oj.uz

Submission #31196

# Submission time Handle Problem Language Result Execution time Memory
31196 2017-08-13T07:04:35 Z leejseo None (KOI16_resort) C++
100 / 100
 0 ms 1196 KB 
#include <stdio.h>
#include <algorithm>

using namespace std;

#define MAX_N 100 // O(N^3)에 돌리면 충분
#define max_coupon(day) ((day)*2)
#define MAX_C max_coupon(MAX_N)
#define MAX_INT 0x7fffffff

int n, m;
int D[MAX_N + 1][MAX_C + 1];
bool skip[MAX_N + 1];

int solve(){
  for (int i = 0; i <= n; i++){
    for(int j=0; j<= 2*i; j++){
      D[i][j] = MAX_INT;
    }
  }
  D[0][0] = 0;
  
  for (int i=0; i<n; i++){
    for (int j=0; j<= 2*i; j++){
      if (D[i][j] == MAX_INT) continue;
      if (skip[i+1]){
        D[i+1][j] = min(D[i+1][j], D[i][j]);
        continue;
      }
      D[i+1][j] = min(D[i+1][j], D[i][j]+10000);
      for (int k=1; k <4; k++){
        if(i+k > n) break;
        D[i+k][j+1] = min(D[i+k][j+1], D[i][j]+25000);
      }
      for (int k=1; k <6; k++){
        if (i+k > n) break;
        D[i+k][j+2] = min(D[i+k][j+2], D[i][j]+37000);
      }
      if (j >= 3) D[i+1][j-3] = min(D[i+1][j-3], D[i][j]);
    }
  }
  int cnt = MAX_INT;
  for (int j=0; j <= 2*n; j++){
    if (cnt > D[n][j]) cnt = D[n][j];
  }
  return cnt;
}

int main(){
  scanf("%d%d", &n, &m);
  for(int i=0; i <= n; i++) skip[i] = false;
  if (m==0){
    int c = solve();
    printf("%d", c);
    return 0;
  }
  for(int i=0; i <= m; i++){
    int ind;
    scanf("%d", &ind);
    skip[ind] = true;
  }
  int c = solve();
  printf("%d", c);
  return 0;
}

Compilation message

resort.cpp: In function 'int main()':
resort.cpp:50:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &n, &m);
                        ^
resort.cpp:59:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &ind);
                      ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1196 KB Output is correct
2 Correct 0 ms 1196 KB Output is correct
3 Correct 0 ms 1196 KB Output is correct
4 Correct 0 ms 1196 KB Output is correct
5 Correct 0 ms 1196 KB Output is correct
6 Correct 0 ms 1196 KB Output is correct
7 Correct 0 ms 1196 KB Output is correct
8 Correct 0 ms 1196 KB Output is correct
9 Correct 0 ms 1196 KB Output is correct
10 Correct 0 ms 1196 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1196 KB Output is correct
2 Correct 0 ms 1196 KB Output is correct
3 Correct 0 ms 1196 KB Output is correct
4 Correct 0 ms 1196 KB Output is correct
5 Correct 0 ms 1196 KB Output is correct
6 Correct 0 ms 1196 KB Output is correct
7 Correct 0 ms 1196 KB Output is correct
8 Correct 0 ms 1196 KB Output is correct
9 Correct 0 ms 1196 KB Output is correct
10 Correct 0 ms 1196 KB Output is correct
11 Correct 0 ms 1196 KB Output is correct
12 Correct 0 ms 1196 KB Output is correct
13 Correct 0 ms 1196 KB Output is correct
14 Correct 0 ms 1196 KB Output is correct
15 Correct 0 ms 1196 KB Output is correct

Subtask #3
72.0 / 72.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1196 KB Output is correct
2 Correct 0 ms 1196 KB Output is correct
3 Correct 0 ms 1196 KB Output is correct
4 Correct 0 ms 1196 KB Output is correct
5 Correct 0 ms 1196 KB Output is correct
6 Correct 0 ms 1196 KB Output is correct
7 Correct 0 ms 1196 KB Output is correct
8 Correct 0 ms 1196 KB Output is correct
9 Correct 0 ms 1196 KB Output is correct
10 Correct 0 ms 1196 KB Output is correct
11 Correct 0 ms 1196 KB Output is correct
12 Correct 0 ms 1196 KB Output is correct
13 Correct 0 ms 1196 KB Output is correct
14 Correct 0 ms 1196 KB Output is correct
15 Correct 0 ms 1196 KB Output is correct
16 Correct 0 ms 1196 KB Output is correct
17 Correct 0 ms 1196 KB Output is correct
18 Correct 0 ms 1196 KB Output is correct
19 Correct 0 ms 1196 KB Output is correct
20 Correct 0 ms 1196 KB Output is correct
21 Correct 0 ms 1196 KB Output is correct
22 Correct 0 ms 1196 KB Output is correct
23 Correct 0 ms 1196 KB Output is correct
24 Correct 0 ms 1196 KB Output is correct
25 Correct 0 ms 1196 KB Output is correct
26 Correct 0 ms 1196 KB Output is correct
27 Correct 0 ms 1196 KB Output is correct
28 Correct 0 ms 1196 KB Output is correct
29 Correct 0 ms 1196 KB Output is correct
30 Correct 0 ms 1196 KB Output is correct
31 Correct 0 ms 1196 KB Output is correct
32 Correct 0 ms 1196 KB Output is correct
33 Correct 0 ms 1196 KB Output is correct
34 Correct 0 ms 1196 KB Output is correct
35 Correct 0 ms 1196 KB Output is correct
36 Correct 0 ms 1196 KB Output is correct
37 Correct 0 ms 1196 KB Output is correct
38 Correct 0 ms 1196 KB Output is correct
39 Correct 0 ms 1196 KB Output is correct
40 Correct 0 ms 1196 KB Output is correct
41 Correct 0 ms 1196 KB Output is correct
42 Correct 0 ms 1196 KB Output is correct
43 Correct 0 ms 1196 KB Output is correct
44 Correct 0 ms 1196 KB Output is correct