# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
71296 |
2018-08-24T10:10:10 Z |
3zp |
매트 (KOI15_mat) |
C++14 |
|
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++){
~~^~~~~~~~~~
# |
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 |
# |
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 |
# |
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 |
# |
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 |
# |
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 |