oj.uz

Submission #71296

# Submission time Handle Problem Language Result Execution time Memory
71296 2018-08-24T10:10:10 Z 3zp 매트 (KOI15_mat) C++14
100 / 100
 561 ms 88240 KB 
#include<bits/stdc++.h>
#define pii pair<int,int>
#define F first
#define S second
using namespace std;
vector<pair<pii,pii> > a, b;
int dp[3009][3009], ans;
int al[3009], ar[3009], ah[3009], ac[3009];
int bl[3009], br[3009], bh[3009], bc[3009];
int P[3009], L[6009], H[3009], C[3009];
int n, w, N;
int fen[3009][6009][2];
void upd(int i, int x, int v, int T){

    while(x <= N){
        fen[i][x][T] = max(fen[i][x][T], v);
        x += (x&-x);
    }
}
int cnT(int i,int x, int T){
    int ans = 0;
    while(x){
        ans = max(ans, fen[i][x][T]);
        x -= (x&-x);
    }
    return ans;
}
main(){
    a . push_back ({{1, 1}, {1 , 0}});
    b . push_back ({{1, 1}, {1 , 0}});

    cin >> n >> w; N = 2*n+6;
    vector<pair<int,int> > v;
    for(int i = 0; i < n; i++){
        cin >> P[i] >> L[i] >> L[i+n] >> H[i] >> C[i];
        v.push_back({L[i], i});
        v.push_back({L[i+n], i + n});
    }
    sort(v.begin(), v.end());
    int cnt = 2;
    for(int i = 0; i < v.size(); i++){
        if(i && v[i].first != v[i-1].first) cnt++;
        L[v[i].second] = cnt;
    }

    for(int i = 0; i < n; i++){
        int p = P[i], l = L[i], r = L[i+n], h = H[i], c = C[i];
        pair<pii, pii >  x = { { l , r } , { h , c } };
        if(p == 0) a .push_back( x );
        else b .push_back( x);
    }
    a.push_back({{2*n+5,2*n+5}, {0,0}});
    b.push_back({{2*n+5,2*n+5}, {0,0}});
    int x = a.size(), y = b.size();
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    dp[0][0] = 0;
    for(int i = 0; i < x; i++)
        al[i] = a[i].F.F,
        ar[i] = a[i].F.S,
        ah[i] = a[i].S.F,
        ac[i] = a[i].S.S;
    for(int i = 0; i < y; i++)
        bl[i] = b[i].F.F,
        br[i] = b[i].F.S,
        bh[i] = b[i].S.F,
        bc[i] = b[i].S.S;
    for(int i = 0; i < x; i++)
        for(int j = 0; j < y; j++){
                if(!((bh[j] + ah[i] <= w ||
                    bl[j] >= ar[i] ||
                    br[j] <= al[i]))) continue;
                dp[i][j] = max(dp[i][j], cnT(j ,min(br[j]-1, al[i]),0) + ac[i]);
                dp[i][j] = max(dp[i][j], cnT(i, min(bl[j],ar[i]), 1) + bc[j]);
                upd(j, ar[i], dp[i][j],0);
                upd(i, br[j], dp[i][j],1);
            ans = max(ans, dp[i][j]);
        }
    cout << ans << endl;
}

Compilation message

mat.cpp:28:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
mat.cpp: In function 'int main()':
mat.cpp:41:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v.size(); i++){
                    ~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 3 ms 648 KB Output is correct
4 Correct 3 ms 648 KB Output is correct
5 Correct 5 ms 656 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 656 KB Output is correct
2 Correct 2 ms 676 KB Output is correct
3 Correct 3 ms 676 KB Output is correct
4 Correct 4 ms 676 KB Output is correct
5 Correct 2 ms 676 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1756 KB Output is correct
2 Correct 5 ms 1888 KB Output is correct
3 Correct 8 ms 1912 KB Output is correct
4 Correct 5 ms 1920 KB Output is correct
5 Correct 5 ms 1924 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 73552 KB Output is correct
2 Correct 108 ms 73552 KB Output is correct
3 Correct 97 ms 73596 KB Output is correct
4 Correct 103 ms 73596 KB Output is correct
5 Correct 85 ms 73596 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 73596 KB Output is correct
2 Correct 541 ms 86572 KB Output is correct
3 Correct 555 ms 87096 KB Output is correct
4 Correct 561 ms 87096 KB Output is correct
5 Correct 403 ms 87096 KB Output is correct
6 Correct 542 ms 88240 KB Output is correct
7 Correct 493 ms 88240 KB Output is correct
8 Correct 304 ms 88240 KB Output is correct
9 Correct 456 ms 88240 KB Output is correct
10 Correct 351 ms 88240 KB Output is correct