oj.uz

답안 #70052

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
70052 2018-08-22T09:51:51 Z mirbek01 Arranging Tickets (JOI17_arranging_tickets) C++17
0 / 100
 3 ms 504 KB 
# include <bits/stdc++.h>

using namespace std;

const int N = 3e2 + 2;

int n, q, a[N], b[N], c[N], dp[5][N][N];
vector < vector <int> > v[N];

int main(){
      cin >> n >> q;

      for(int i = 1; i <= q; i ++){
            cin >> a[i] >> b[i] >> c[i];
            vector <int> vec;
            for(int j = a[i]; j < b[i]; j ++)
                  vec.push_back(j);
            v[i].push_back(vec);
            vec.clear();
            for(int j = a[i]; j <= b[i]; j ++)
                  vec.push_back(j);
            v[i].push_back(vec);
            vec.clear();
            for(int j = a[i]; j >= 1; j --)
                  vec.push_back(j);
            for(int j = n; j > b[i]; j --)
                  vec.push_back(j);
            v[i].push_back(vec);
            vec.clear();
            for(int j = a[i] - 1; j >= 1; j --)
                  vec.push_back(j);
            for(int j = n; j >= b[i]; j --)
                  vec.push_back(j);
            v[i].push_back(vec);
      }

      for(int i = 1; i <= q; i ++){
            for(int j = 1; j <= 4; j ++){
                  for(int k : v[i][j - 1])
                        dp[j][i][k] ++;
                  vector <int> cnt(n + 1, 0);
                  int mn = 1e9, id;
                  for(int k = 1; k <= 4; k ++){
                        int mx = 0;
                        for(int t = 1; t <= n; t ++){
                              mx = max(mx, dp[j][i][t] + dp[k][i - 1][t]);
                        }
                        if(mx < mn){
                              mn = mx, id = k;
                        }
                  }
                  for(int t = 1; t <= n; t ++)
                        dp[j][i][t] += dp[id][i - 1][t];
            }
      }

      int ans = 1e9;

      for(int i = 1; i <= 4; i ++){
            int mx = 0;
            for(int j = 1; j <= n; j ++)
                  mx = max(mx, dp[i][q][j]);
            ans = min(ans, mx);
      }

      cout << ans << endl;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 35.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 15.0

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