제출 #70057

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
70057		Talant	Arranging Tickets (JOI17_arranging_tickets)	C++17	0 / 100	3 ms	380 KiB

arranging_tickets

#include <bits/stdc++.h>

#define mk make_pair
#define sc second
#define fr first
#define pb emplace_back
#define all(s) s.begin(), s.end()
#define sz(s) ( (int)s.size() )
#define Scan(a) scanf ("%I64d", &a)
#define scan(a) scanf ("%d", &a)
#define int long long

using namespace std;

const int inf = (int)1e9 + 7;
const int N = (int)2e5 + 7;

int n,m;
int a[N],b[N],f[N];
int dp[N][3];
int c[N],d[N];
int c1[N],d1[N];

main () {
      cin >> n >> m;

      for (int i = 1; i <= m; i ++) {
            cin >> a[i] >> b[i] >> f[i];
      }

      for (int i = a[1]; i < b[1]; i ++) c[i] ++;
      for (int i = 1; i <= n; i ++) {
            if (a[1] <= i && i < b[1]) continue;
            d[i] ++;
      }
      dp[1][0] = dp[1][1] = 1;

      for (int i = 2; i <= m; i ++) {
            int mx = 0,mx1 = 0;
            for (int j = 1; j <= n; j ++) {
                  if (a[i] <= j && j < b[i]) mx = max(mx,c[j] + 1);
                  mx = max(mx,c[j]);
            }
            for (int j = 1; j <= n; j ++) {
                  if (a[i] <= j && j < b[i]) mx1 = max(mx1,d[j] + 1);
                  mx1 = max(mx1,d[j]);
            }
            int mxx = 0,mxx1 = 0;
            for (int j = 1; j <= n; j ++) {
                  mxx = max(mxx,c[j]);
                  if (a[i] <= j && j < b[i])
                        continue;
                  mx = max(mxx,c[j] + 1);
            }
            for (int j = 1; j <= n; j ++) {
                  mxx1 = max(mxx1,d[j]);
                  if (a[i] <= j && j < b[i])
                        continue;
                  mxx1 = max(mxx1,d[j] + 1);
            }
            if (mx > mx1) {
                  dp[i][0] = mx1;
                  for (int j = 1; j <= n; j ++) {
                        if (a[i] <= j && j < b[i]) c1[j] = d[j] + 1;
                        else c1[j] = d[j];
                  }
            }
            else {
                  dp[i][0] = mx;
                  for (int j = 1; j <= n; j ++) {
                        if (a[i] <= j && j < b[i]) c1[j] = c[j] + 1;
                        else c1[j] = c[j];
                  }
            }
            if (mxx > mxx1) {
                  dp[i][1] = mxx1;
                  for (int j = 1; j <= n; j ++) {
                        if (a[i] <= j && j < b[i]) d1[j] = d[j] + 1;
                        else d1[j] = d[j];
                  }
            }
            else {
                  dp[i][1] = mxx;
                  for (int j = 1; j <= n; j ++) {
                        if (a[i] <= j && j < b[i]) d1[j] = c[j] + 1;
                        else d1[j] = c[j];
                  }
            }
            for (int j = 1; j <= n; j ++) swap(c1[j],c[j]),swap(d1[j],d[j]);
      }
      cout << min(dp[m][0],dp[m][1]) << endl;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 35
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 15