| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 584909 |
2022-06-28T06:38:17 Z |
박상훈(#8379) |
도장 모으기 (JOI14_stamps) |
C++14 |
|
1000 ms |
143972 KB |
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll INF = 4e18;
struct Seg{
ll tree[6060];
int sz;
void init(int n){
sz = n;
fill(tree, tree+sz*2, INF);
}
void update(int p, ll x){
p += sz;
for (tree[p]=min(tree[p], x);p>1;p>>=1) tree[p>>1] = min(tree[p], tree[p^1]);
}
ll query(int l, int r){
r++;
ll ret = INF;
for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
if (l&1) ret = min(ret, tree[l++]);
if (r&1) ret = min(ret, tree[--r]);
}
return ret;
}
}M1, M3[3030];
struct Seg2{
ll tree[6060];
int sz;
void init(int n){
sz = n;
fill(tree, tree+sz*2, INF);
}
ll query(int p){
p += sz;
ll ret = tree[p];
for (p>>=1;p;p>>=1) ret = min(ret, tree[p]);
return ret;
}
void update(int l, int r, ll x){
r++;
for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
if (l&1){
tree[l] = min(tree[l], x);
l++;
}
if (r&1){
--r;
tree[r] = min(tree[r], x);
}
}
}
}M2;
ll dp[3030][3030], cstS[3030], dcstS[3030], UD[3030], DU[3030], T;
ll cst(int l, int r){
if (r<l) return 0;
return cstS[r] - cstS[l-1];
}
ll dcst(int l, int r){
if (r<l) return 0;
return cstS[r] - cstS[l-1] - (dcstS[r] - dcstS[l-1]);
}
ll Tij(int r, int l){
return T*(r-l)*2 + UD[r] + DU[l];
}
int main(){
int n;
scanf("%d %lld", &n, &T);
for (int i=1;i<=n;i++){
int u, v, d, e;
scanf("%d %d %d %d", &u, &v, &d, &e);
UD[i] = u + e;
DU[i] = d + v;
int uu = u+v, dd = d+e;
cstS[i] = cstS[i-1] + uu;
dcstS[i] = dcstS[i-1] + max(uu-dd, 0);
M3[i].init(n+1);
}
M1.init(n+1);
M2.init(n+1);
ll ans = T*(n+1) + cst(1, n);
for (int i=1;i<=n;i++){
for (int j=1;j<i;j++){
dp[i][j] = T*i + cst(1, j-1) + dcst(j+1, i-1) + Tij(i, j);
///case 1. k<=j
dp[i][j] = min(dp[i][j], M1.query(1, j-1) + T*i - cst(j, n) + dcst(j+1, i-1) + Tij(i, j));
dp[i][j] = min(dp[i][j], M1.query(j, j) + T*i - cst(j+1, n) + dcst(j+1, i-1) + Tij(i, j));
///case 2. k>j, l<j
//dp[i][j] = min(dp[i][j], M2.query(j) + T*i - dcst(i, n) + Tij(i, j) - dcst(j, j));
///case 3. k>j, l=j
//dp[i][j] = min(dp[i][j], M3[j].query(j+1, i-1) + T*i - dcst(i, n) + Tij(i, j));
ll m1 = INF, m2 = INF, m3 = INF;
for (int k=1;k<=j;k++){
for (int l=1;l<k;l++){
///case 1. k<=j
m1 = min(m1, dp[k][l] - T*k + cst(k+1, n));
//dp[i][j] = min(dp[i][j], dp[k][l] + T*(i-k) + cst(k+1, j-1) + dcst(j+1, i-1) + Tij(i, j));
}
}
for (int k=j+1;k<=i;k++){
for (int l=1;l<j;l++){
///case 2. k>j, l<j
m2 = min(m2, dp[k][l] - T*k + dcst(k+1, n));
dp[i][j] = min(dp[i][j], dp[k][l] + T*(i-k) + dcst(k+1, i-1) + Tij(i, j) - dcst(j, j));
}
if (k==i) break;
///case 3.k>j, l=j
int l = j;
m3 = min(m3, dp[k][l] - T*k + dcst(k+1, n));
dp[i][j] = min(dp[i][j], dp[k][l] + T*(i-k) + dcst(k+1, i-1) + Tij(i, j));
}
assert(m1==M1.query(1, j));
assert(m2==M2.query(j));
assert(m3==M3[j].query(j+1, i-1));
ans = min(ans, dp[i][j] + T*(n+1-i) + cst(i+1, n));
///update
M1.update(i, dp[i][j] - T*i + cst(i+1, n));
M2.update(j+1, i-1, dp[i][j] - T*i + dcst(i+1, n));
M3[j].update(i, dp[i][j] - T*i + dcst(i+1, n));
}
}
//printf("%lld\n", dp[2][1]);
printf("%lld\n", ans);
return 0;
}
Compilation message
stamps.cpp: In function 'int main()':
stamps.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
72 | scanf("%d %lld", &n, &T);
| ~~~~~^~~~~~~~~~~~~~~~~~~
stamps.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
75 | scanf("%d %d %d %d", &u, &v, &d, &e);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
468 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
468 KB |
Output is correct |
| 8 |
Correct |
1 ms |
468 KB |
Output is correct |
| 9 |
Correct |
1 ms |
468 KB |
Output is correct |
| 10 |
Correct |
1 ms |
468 KB |
Output is correct |
| 11 |
Correct |
1 ms |
468 KB |
Output is correct |
| 12 |
Correct |
1 ms |
468 KB |
Output is correct |
| 13 |
Correct |
1 ms |
480 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
1236 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
22 ms |
1336 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
468 KB |
Output is correct |
| 6 |
Correct |
4 ms |
852 KB |
Output is correct |
| 7 |
Correct |
20 ms |
1132 KB |
Output is correct |
| 8 |
Correct |
18 ms |
1236 KB |
Output is correct |
| 9 |
Correct |
19 ms |
1284 KB |
Output is correct |
| 10 |
Correct |
23 ms |
1252 KB |
Output is correct |
| 11 |
Correct |
20 ms |
1272 KB |
Output is correct |
| 12 |
Correct |
20 ms |
1252 KB |
Output is correct |
| 13 |
Correct |
20 ms |
1292 KB |
Output is correct |
| 14 |
Correct |
23 ms |
1320 KB |
Output is correct |
| 15 |
Correct |
24 ms |
1364 KB |
Output is correct |
| 16 |
Correct |
20 ms |
1308 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1084 ms |
143972 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
