Submission #70216

#	Time	Username	Problem	Language	Result	Execution time	Memory
70216		mirbek01	Arranging Tickets (JOI17_arranging_tickets)	C++17	0 / 100	3 ms	376 KiB

arranging_tickets

# 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];
            if(a[i] > b[i]) swap(a[i], b[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
• Subtask 2: 0 / 35
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 15