Algoogle

Algorithm for Programming Contest

AOJ 2176 For the Peace

Category: AOJ Tag: greedy

For the Peace

問題概要


解法


入力は新しい順ということに注意する.
greedyに取り除けるものを取り除いていけばよい.

コード


(2176.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>

#define repi(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,a) repi(i,0,a)
#define all(u) (u).begin(),(u).end()
using namespace std;
typedef vector<int> vi;

int n, d;

int main(){
    while(cin >> n >> d, n || d){
        vector<vi> missiles(n);
        vi cap(n,0);
        rep(i,n){
            int m, c;
            cin >> m;
            missiles[i].resize(m);
            rep(j,m){
                cin >> missiles[i][j];
                cap[i] += missiles[i][j];
            }
        }
        while(true){
            bool erased = false;
            rep(i,n)if(missiles[i].size()){
                while(missiles[i].size()){
                    cap[i] -= missiles[i].back();
                    if(*max_element(all(cap)) - cap[i] <= d){
                        missiles[i].pop_back();
                        erased = true;
                    }
                    else {
                        cap[i] += missiles[i].back();
                        break;
                    }
                }
            }
            if(!erased) break;
        }
        bool ok = true;
        rep(i,n) if(missiles[i].size()) ok = false;
        cout << (ok? "Yes": "No") << endl;
    }
    return 0;
}

Comments