oj.uz

답안 #244898

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
244898 2020-07-05T08:56:16 Z Nightlight Collecting Stamps 3 (JOI20_ho_t3) C++14
0 / 100
 39 ms 67968 KB 
#include <bits/stdc++.h>
#define pii pair<int, int>
#define INF 0x3f3f3f3f
using namespace std;

int N, K, L;
priority_queue<tuple<int, int, int, int, bool>> pq;
int pos[205];
int T[205];
int dist[205][205][205][2];
int jrk[205][205];

int jarak(int a, int b) {
  if(jrk[a][b] != -1) return jrk[a][b];
  if(pos[a] > pos[b]) swap(a, b);
//  cout << a << " " << b << " -> " << min(pos[b] - pos[a], pos[a] + L - pos[b]) << "\n"; 
  return jrk[a][b] = min(pos[b] - pos[a], pos[a] + L - pos[b]);
}

int main() {
  scanf("%d %d", &N, &L);
  memset(dist, INF, sizeof(dist));
  memset(jrk, -1, sizeof(jrk));
  for(int i = 1; i <= N; i++) scanf("%d", &pos[i]);
  for(int i = 1; i <= N; i++) scanf("%d", &T[i]);
  int now = jarak(0, N);
  int ada = now <= T[N] ? 1 : 0;
//  cout << now << " " << ada << "\n";
  pq.emplace(now, N, 0, ada, 0);
  dist[N][0][ada][0] = now;
  now = jarak(0, 1);
  ada = now <= T[1] ? 1 : 0;
  pq.emplace(now, 0, 1, ada, 1);
  dist[0][1][ada][1] = now;
  int poscur;
  int t, l, r, cnt, side;
  while(!pq.empty()) {
    tie(t, l, r, cnt, side) = pq.top();
    pq.pop();
    if(t > 1000000000 || l - 1 <= r || r + 1 >= l || r == N) continue;
    poscur = side ? r : l;
    if(l == 0) {
      now = jarak(N, poscur) + t;
      ada = cnt + (now <= T[N] ? 1 : 0);
      if(dist[N][r][ada][0] > now) {
        dist[N][r][ada][0] = now;
        pq.emplace(now, N, r, ada, 0);
      }
    }else {
      now = jarak(poscur, l - 1) + t;
      ada = cnt + (now <= T[l - 1] ? 1 : 0);
      if(dist[l - 1][r][ada][0] > now) {
        dist[l - 1][r][ada][0] = now;
        pq.emplace(now, l - 1, r, ada, 0);
      }
    }
    now = jarak(poscur, r + 1) + t;
    ada = cnt + (now <= T[r + 1] ? 1 : 0);
    if(dist[l][r + 1][ada][1] > now) {
      dist[l][r + 1][ada][1] = now;
      pq.emplace(now, l, r + 1, ada, 1);
    }
  }
  int ans = 0;
  for(int i = 0; i <= N; i++) {
    for(int j = 0; j <= N; j++) {
      for(int k = 1; k <= N; k++) {
        if(k > ans && (dist[i][j][k][0] < INF || dist[i][j][k][1] < INF)) ans = k; 
      }
    }  
  }
  cout << ans << "\n";
  cin >> N;
}

Compilation message

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:21: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:24:36: 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", &pos[i]);
                               ~~~~~^~~~~~~~~~~~~~~
ho_t3.cpp:25:36: 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 Correct 39 ms 67968 KB Output is correct
2 Incorrect 39 ms 67960 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 67968 KB Output is correct
2 Incorrect 39 ms 67960 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 67968 KB Output is correct
2 Incorrect 39 ms 67960 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 67968 KB Output is correct
2 Incorrect 39 ms 67960 KB Output isn't correct
3 Halted 0 ms 0 KB -