oj.uz

답안 #208937

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
208937 2020-03-12T15:41:38 Z eriksuenderhauf Collecting Stamps 3 (JOI20_ho_t3) C++11
0 / 100
 81 ms 135160 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e2 + 5;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int X[N], T[N], n, l, ans = 0;
ll dp[N][N][N][2];

ll dist(int i, int j) { return min(abs(X[i]-X[j]), l - abs(X[i]-X[j])); }
void ckmn(ll& x, ll y) { x = min(x, y); }

int main() {
  scanf("%d %d", &n, &l);
  for (int i = 1; i <= n; i++) scanf("%d", X+i);
  for (int i = 1; i <= n; i++) scanf("%d", T+i);
  memset(dp, 0x3f, sizeof dp);
  dp[0][0][0][0] = dp[0][0][0][1] = 0;
  for (int i = 0; i < n; i++) {
    for (int r = 0, l = i; r <= i; r++, l--) {
      ll v;
      for (int k = 0; k <= i; k++) {
        v = dp[l][r][k][0] + dist(n+1-l, n-l);
        ckmn(dp[l+1][r][k + v <= T[n-l]][0], v);
        v = dp[l][r][k][0] + dist(n+1-l, r+1);
        ckmn(dp[l][r+1][k + v <= T[r+1]][1], v);
        v = dp[l][r][k][1] + dist(r, n-l);
        ckmn(dp[l+1][r][k + v <= T[n-l]][0], v);
        v = dp[l][r][k][1] + dist(r, r+1);
        ckmn(dp[l][r+1][k + v <= T[r+1]][1], v);
      }
    }
  }
  for (int i = 0; i <= n; i++)
    for (int j = 0; j <= n; j++)
      for (int k = 0; k <= n; k++)
        for (int f = 0; f < 2; f++)
          if (dp[i][j][k][f] != inf)
            ans = max(ans, k);
  printf("%d\n", ans);
}

Compilation message

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:13:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &n, &l);
   ~~~~~^~~~~~~~~~~~~~~~~
ho_t3.cpp:14:37: 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", X+i);
                                ~~~~~^~~~~~~~~~~
ho_t3.cpp:15:37: 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", T+i);
                                ~~~~~^~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 81 ms 135160 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 81 ms 135160 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 81 ms 135160 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 81 ms 135160 KB Output isn't correct
2 Halted 0 ms 0 KB -