oj.uz

Submission #884715

# Submission time Handle Problem Language Result Execution time Memory
884715 2023-12-08T08:23:04 Z mgl_diamond Arranging Tickets (JOI17_arranging_tickets) C++17
10 / 100
 346 ms 2644 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;

#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l); i>=(r); --i)
#define fore(x, v) for(auto &x : v)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define file "input"

template<class T> bool minimize(T &a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T> bool maximize(T &a, T b) { if (a < b) { a = b; return 1; } return 0; }

void setIO() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  if (fopen(file".inp", "r")) {
    freopen(file".inp", "r", stdin);
    freopen(file".out", "w", stdout);
  }
}

const int N = 2e5+5;
int n, m, a[N], b[N], c[N];

int cnt[N];
int mx;

void inc(int l, int r, bool t) {
  if (l > r) swap(l, r);
  if (!t) foru(i, l, r-1) maximize(mx, ++cnt[i]);
  else {
    foru(i, 1, l-1) maximize(mx, ++cnt[i]);
    foru(i, r, n) maximize(mx, ++cnt[i]);
  }
}

int main() {
	setIO();

	cin >> n >> m;
	foru(i, 1, m) {
		cin >> a[i] >> b[i] >> c[i];
	}
	foru(i, 1, m) {
    while (c[i]-->1) {
      ++m;
      a[m] = a[i];
      b[m] = b[i];
    }
	}
	int mn = N;
	for(int mask=0; mask<(1<<m); ++mask) {
    foru(i, 1, n) cnt[i] = 0;
    mx = 0;
    foru(i, 1, m)
      if (mask >> (i-1) & 1) {
        inc(a[i], b[i], 0);
      }
      else {
        inc(a[i], b[i], 1);
      }
    minimize(mn, mx);
	}
	cout << mn;
}

Compilation message

arranging_tickets.cpp: In function 'void setIO()':
arranging_tickets.cpp:22:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     freopen(file".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
arranging_tickets.cpp:23:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     freopen(file".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 2492 KB Output is correct
2 Correct 340 ms 2644 KB Output is correct
3 Correct 336 ms 2396 KB Output is correct
4 Correct 328 ms 2496 KB Output is correct
5 Correct 333 ms 2496 KB Output is correct
6 Correct 346 ms 2504 KB Output is correct
7 Correct 334 ms 2516 KB Output is correct
8 Correct 329 ms 2496 KB Output is correct
9 Correct 330 ms 2496 KB Output is correct
10 Correct 338 ms 2392 KB Output is correct
11 Correct 341 ms 2496 KB Output is correct
12 Correct 339 ms 2496 KB Output is correct
13 Correct 339 ms 2640 KB Output is correct
14 Correct 329 ms 2396 KB Output is correct
15 Correct 330 ms 2396 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 2492 KB Output is correct
2 Correct 340 ms 2644 KB Output is correct
3 Correct 336 ms 2396 KB Output is correct
4 Correct 328 ms 2496 KB Output is correct
5 Correct 333 ms 2496 KB Output is correct
6 Correct 346 ms 2504 KB Output is correct
7 Correct 334 ms 2516 KB Output is correct
8 Correct 329 ms 2496 KB Output is correct
9 Correct 330 ms 2496 KB Output is correct
10 Correct 338 ms 2392 KB Output is correct
11 Correct 341 ms 2496 KB Output is correct
12 Correct 339 ms 2496 KB Output is correct
13 Correct 339 ms 2640 KB Output is correct
14 Correct 329 ms 2396 KB Output is correct
15 Correct 330 ms 2396 KB Output is correct
16 Incorrect 149 ms 2392 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 2492 KB Output is correct
2 Correct 340 ms 2644 KB Output is correct
3 Correct 336 ms 2396 KB Output is correct
4 Correct 328 ms 2496 KB Output is correct
5 Correct 333 ms 2496 KB Output is correct
6 Correct 346 ms 2504 KB Output is correct
7 Correct 334 ms 2516 KB Output is correct
8 Correct 329 ms 2496 KB Output is correct
9 Correct 330 ms 2496 KB Output is correct
10 Correct 338 ms 2392 KB Output is correct
11 Correct 341 ms 2496 KB Output is correct
12 Correct 339 ms 2496 KB Output is correct
13 Correct 339 ms 2640 KB Output is correct
14 Correct 329 ms 2396 KB Output is correct
15 Correct 330 ms 2396 KB Output is correct
16 Incorrect 149 ms 2392 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 2492 KB Output is correct
2 Correct 340 ms 2644 KB Output is correct
3 Correct 336 ms 2396 KB Output is correct
4 Correct 328 ms 2496 KB Output is correct
5 Correct 333 ms 2496 KB Output is correct
6 Correct 346 ms 2504 KB Output is correct
7 Correct 334 ms 2516 KB Output is correct
8 Correct 329 ms 2496 KB Output is correct
9 Correct 330 ms 2496 KB Output is correct
10 Correct 338 ms 2392 KB Output is correct
11 Correct 341 ms 2496 KB Output is correct
12 Correct 339 ms 2496 KB Output is correct
13 Correct 339 ms 2640 KB Output is correct
14 Correct 329 ms 2396 KB Output is correct
15 Correct 330 ms 2396 KB Output is correct
16 Incorrect 149 ms 2392 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 2492 KB Output is correct
2 Correct 340 ms 2644 KB Output is correct
3 Correct 336 ms 2396 KB Output is correct
4 Correct 328 ms 2496 KB Output is correct
5 Correct 333 ms 2496 KB Output is correct
6 Correct 346 ms 2504 KB Output is correct
7 Correct 334 ms 2516 KB Output is correct
8 Correct 329 ms 2496 KB Output is correct
9 Correct 330 ms 2496 KB Output is correct
10 Correct 338 ms 2392 KB Output is correct
11 Correct 341 ms 2496 KB Output is correct
12 Correct 339 ms 2496 KB Output is correct
13 Correct 339 ms 2640 KB Output is correct
14 Correct 329 ms 2396 KB Output is correct
15 Correct 330 ms 2396 KB Output is correct
16 Incorrect 149 ms 2392 KB Output isn't correct
17 Halted 0 ms 0 KB -