oj.uz

Submission #156064

# Submission time Handle Problem Language Result Execution time Memory
156064 2019-10-03T06:54:05 Z HungAnhGoldIBO2020 도장 모으기 (JOI14_stamps) C++14
100 / 100
 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

stamps.cpp: In function 'int main()':
stamps.cpp:10:12: warning: unused variable 'k' [-Wunused-variable]
  int n,i,j,k,l,t;
            ^
stamps.cpp:10:14: warning: unused variable 'l' [-Wunused-variable]
  int n,i,j,k,l,t;
              ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory 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

Subtask #2
75.0 / 75.0

# Verdict Execution time Memory 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

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory 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