| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 156064 | 2019-10-03T06:54:05 Z | HungAnhGoldIBO2020 | 도장 모으기 (JOI14_stamps) | C++14 | 334 ms | 212244 KB |
#include<iostream>
using namespace std;
#define int long long
const int N=3e3+2;
const int inf=1e15+2;
int dp[N][N],u[N],v[N],d[N],e[N],min1[N][N],min2[N][N];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,i,j,k,l,t;
cin>>n>>t;
for(i=1;i<=n;i++){
cin>>u[i]>>v[i]>>d[i]>>e[i];
}
for(i=0;i<=n;i++){
for(j=0;j<=n;j++){
dp[i][j]=inf;
if(i==0){
min1[i][j]=0;
}
else{
min1[i][j]=inf;
}
min2[i][j]=inf;
}
}
dp[0][0]=0;
for(i=1;i<=n;i++){
for(j=0;j<=n;j++){
if(j){
dp[i][j]=min(dp[i][j],dp[i-1][j]+min(d[i]+e[i],u[i]+v[i])+2*j*t);
}
else{
dp[i][j]=min(dp[i][j],dp[i-1][j]+u[i]+v[i]+2*j*t);
}
}
for(j=0;j<=n;j++){
if(j!=n){
dp[i][j]=min(dp[i][j],min2[i-1][j+1]-j*(u[i]+e[i])+2*j*t);
}
if(j){
dp[i][j]=min(dp[i][j],min1[i-1][j-1]+j*(d[i]+v[i])+2*j*t);
min1[i][j]=min(min1[i][j-1],dp[i][j]-j*(d[i+1]+v[i+1]));
}
else{
min1[i][j]=dp[i][j]-j*(d[i+1]+v[i+1]);
}
}
for(j=n;j>=0;j--){
if(j!=n){
min2[i][j]=min(min2[i][j+1],dp[i][j]+j*(u[i+1]+e[i+1]));
}
else{
min2[i][j]=dp[i][j]+j*(u[i+1]+e[i+1]);
}
}
// for(j=0;j<=n;j++){
// cout<<dp[i][j]<<' ';
// }
// cout<<endl;
}
cout<<dp[n][0]+t*(n+1);
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 504 KB | Output is correct |
| 2 | Correct | 2 ms | 376 KB | Output is correct |
| 3 | Correct | 2 ms | 632 KB | Output is correct |
| 4 | Correct | 2 ms | 504 KB | Output is correct |
| 5 | Correct | 2 ms | 504 KB | Output is correct |
| 6 | Correct | 2 ms | 504 KB | Output is correct |
| 7 | Correct | 2 ms | 504 KB | Output is correct |
| 8 | Correct | 2 ms | 632 KB | Output is correct |
| 9 | Correct | 2 ms | 632 KB | Output is correct |
| 10 | Correct | 2 ms | 632 KB | Output is correct |
| 11 | Correct | 2 ms | 632 KB | Output is correct |
| 12 | Correct | 2 ms | 632 KB | Output is correct |
| 13 | Correct | 2 ms | 632 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 3 ms | 1656 KB | Output is correct |
| 2 | Correct | 2 ms | 376 KB | Output is correct |
| 3 | Correct | 3 ms | 1784 KB | Output is correct |
| 4 | Correct | 2 ms | 504 KB | Output is correct |
| 5 | Correct | 2 ms | 760 KB | Output is correct |
| 6 | Correct | 3 ms | 1144 KB | Output is correct |
| 7 | Correct | 3 ms | 1656 KB | Output is correct |
| 8 | Correct | 3 ms | 1784 KB | Output is correct |
| 9 | Correct | 4 ms | 1784 KB | Output is correct |
| 10 | Correct | 4 ms | 1784 KB | Output is correct |
| 11 | Correct | 3 ms | 1912 KB | Output is correct |
| 12 | Correct | 3 ms | 1784 KB | Output is correct |
| 13 | Correct | 3 ms | 1784 KB | Output is correct |
| 14 | Correct | 3 ms | 1912 KB | Output is correct |
| 15 | Correct | 3 ms | 1912 KB | Output is correct |
| 16 | Correct | 3 ms | 1784 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 272 ms | 211832 KB | Output is correct |
| 2 | Correct | 2 ms | 376 KB | Output is correct |
| 3 | Correct | 272 ms | 212244 KB | Output is correct |
| 4 | Correct | 229 ms | 187128 KB | Output is correct |
| 5 | Correct | 188 ms | 155144 KB | Output is correct |
| 6 | Correct | 85 ms | 72184 KB | Output is correct |
| 7 | Correct | 53 ms | 45304 KB | Output is correct |
| 8 | Correct | 274 ms | 211912 KB | Output is correct |
| 9 | Correct | 273 ms | 211928 KB | Output is correct |
| 10 | Correct | 275 ms | 212072 KB | Output is correct |
| 11 | Correct | 272 ms | 212088 KB | Output is correct |
| 12 | Correct | 275 ms | 212172 KB | Output is correct |
| 13 | Correct | 295 ms | 212104 KB | Output is correct |
| 14 | Correct | 334 ms | 212116 KB | Output is correct |
| 15 | Correct | 303 ms | 212216 KB | Output is correct |
| 16 | Correct | 280 ms | 212112 KB | Output is correct |
| 17 | Correct | 273 ms | 212084 KB | Output is correct |