oj.uz

Submission #129705

# Submission time Handle Problem Language Result Execution time Memory
129705 2019-07-13T05:11:53 Z 박상수(#3145) 도장 모으기 (JOI14_stamps) C++14
100 / 100
 184 ms 72440 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>
#include <bitset>
#include <time.h>
#include <limits.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb push_back
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;

int N, T;
ll dp[3030][3030];
int U[3030], V[3030], D[3030], E[3030];

int main() {
	scanf("%d%d", &N, &T);
	for(int i=1;i<=N;i++) scanf("%d%d%d%d", U+i, V+i, D+i, E+i);
	rep(i, 3030) rep(j, 3030) dp[i][j] = 1e18;
	dp[0][0] = T;
	auto upd = [&](ll &a, ll b) { if(a > b) a = b; };
	for(int i=0;i<N;i++) {
		for(int j=0;j<=N;j++) if(dp[i][j] < 1e17){
			upd(dp[i+1][j], dp[i][j] + U[i+1] + V[i+1]);
			if(j >= 1) upd(dp[i+1][j-1], dp[i][j] + U[i+1] + E[i+1]);
			upd(dp[i+1][j+1], dp[i][j] + D[i+1] + V[i+1]);
			if(j >= 1) upd(dp[i+1][j], dp[i][j] + D[i+1] + E[i+1]);
		}
		for(int j=N;j>=0;j--) dp[i+1][j] = min(dp[i+1][j], dp[i+1][j+1] + U[i+1] + E[i+1]);
		for(int j=0;j<=N;j++) dp[i+1][j] += (2*j+1) * T;
		for(int j=1;j<=N;j++) dp[i+1][j] = min(dp[i+1][j], dp[i+1][j-1] + 2 * T + D[i+1] + V[i+1]);
	}
	printf("%lld\n", dp[N][0]);
	return 0;
}

Compilation message

stamps.cpp: In function 'int main()':
stamps.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &T);
  ~~~~~^~~~~~~~~~~~~~~~
stamps.cpp:38:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=N;i++) scanf("%d%d%d%d", U+i, V+i, D+i, E+i);
                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 72184 KB Output is correct
2 Correct 59 ms 72184 KB Output is correct
3 Correct 60 ms 72184 KB Output is correct
4 Correct 60 ms 72120 KB Output is correct
5 Correct 60 ms 72184 KB Output is correct
6 Correct 60 ms 72248 KB Output is correct
7 Correct 59 ms 72188 KB Output is correct
8 Correct 59 ms 72184 KB Output is correct
9 Correct 59 ms 72184 KB Output is correct
10 Correct 60 ms 72220 KB Output is correct
11 Correct 59 ms 72184 KB Output is correct
12 Correct 59 ms 72188 KB Output is correct
13 Correct 59 ms 72184 KB Output is correct

Subtask #2
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 72372 KB Output is correct
2 Correct 59 ms 72196 KB Output is correct
3 Correct 59 ms 72184 KB Output is correct
4 Correct 59 ms 72184 KB Output is correct
5 Correct 60 ms 72184 KB Output is correct
6 Correct 59 ms 72184 KB Output is correct
7 Correct 59 ms 72156 KB Output is correct
8 Correct 59 ms 72188 KB Output is correct
9 Correct 67 ms 72184 KB Output is correct
10 Correct 60 ms 72184 KB Output is correct
11 Correct 60 ms 72224 KB Output is correct
12 Correct 59 ms 72200 KB Output is correct
13 Correct 60 ms 72184 KB Output is correct
14 Correct 59 ms 72180 KB Output is correct
15 Correct 73 ms 72184 KB Output is correct
16 Correct 59 ms 72184 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 72336 KB Output is correct
2 Correct 59 ms 72184 KB Output is correct
3 Correct 177 ms 72312 KB Output is correct
4 Correct 152 ms 72364 KB Output is correct
5 Correct 131 ms 72312 KB Output is correct
6 Correct 91 ms 72284 KB Output is correct
7 Correct 79 ms 72312 KB Output is correct
8 Correct 180 ms 72312 KB Output is correct
9 Correct 180 ms 72312 KB Output is correct
10 Correct 177 ms 72440 KB Output is correct
11 Correct 179 ms 72348 KB Output is correct
12 Correct 180 ms 72312 KB Output is correct
13 Correct 184 ms 72232 KB Output is correct
14 Correct 178 ms 72344 KB Output is correct
15 Correct 181 ms 72384 KB Output is correct
16 Correct 184 ms 72312 KB Output is correct
17 Correct 182 ms 72324 KB Output is correct