oj.uz

Submission #300395

# Submission time Handle Problem Language Result Execution time Memory
300395 2020-09-17T06:39:58 Z kevlee Carnival Tickets (IOI20_tickets) C++17
27 / 100
 951 ms 79112 KB 
#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mod 1000000007
#define inf 1000000000
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pii>
#define SET(a, b) memset(a, b, sizeof(a))
#define all(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
priority_queue <pll> pq[1505];
bool used[1505][1505];
pll a[1505];
long long find_maximum(int k, vector<vi> x) {
	int n = x.size();
	int m = x[0].size();
	vector <vi> answer;
  vi row(m, -1);
	FOR(i, 0, n-1) {
		answer.pb(row);
	}
  ll sum = 0;
  FOR(i, 0, n-1) {
    FOR(j, m-k, m-1) {
      pq[i].push({-x[i][j] - x[i][j-m+k], j});
    }
  }
  FOR(i, 0, k-1) {
    FOR(j, 0, n-1) {
      a[j] = {pq[j].top().fi, j};
    }
    sort(a, a+n);
    reverse(a, a+n);
    FOR(j, 0, n/2 - 1) {
      auto tmp = pq[a[j].se].top();
      pq[a[j].se].pop();
      sum -= x[a[j].se][tmp.se-m+k];
      used[a[j].se][i] = true;
      answer[a[j].se][tmp.se-m+k] = i;
    }
  }
  FOR(i, 0, n-1) {
    int cur = 0;
    FORD(j, m-1, m-k) {
      //if (answer[i][j-m+k] != -1) continue; 
      while (cur < k && used[i][cur]) cur++;
      if (cur >= k) break;
      sum += x[i][j];
      answer[i][j] = cur;
      cur++;
    }
  }
	allocate_tickets(answer);
	return sum;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 768 KB Output is correct
6 Correct 3 ms 2688 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 4 ms 640 KB Output is correct
5 Correct 43 ms 2936 KB Output is correct
6 Correct 823 ms 53368 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 3 ms 768 KB Output is correct
5 Correct 29 ms 4152 KB Output is correct
6 Correct 890 ms 78228 KB Output is correct
7 Correct 951 ms 79112 KB Output is correct
8 Incorrect 7 ms 1024 KB There is no ticket of color 0 on day 60
9 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB There is no ticket of color 0 on day 1
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB There is no ticket of color 0 on day 1
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB There is no ticket of color 0 on day 1
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 768 KB Output is correct
6 Correct 3 ms 2688 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 4 ms 640 KB Output is correct
11 Correct 43 ms 2936 KB Output is correct
12 Correct 823 ms 53368 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 3 ms 768 KB Output is correct
17 Correct 29 ms 4152 KB Output is correct
18 Correct 890 ms 78228 KB Output is correct
19 Correct 951 ms 79112 KB Output is correct
20 Incorrect 7 ms 1024 KB There is no ticket of color 0 on day 60
21 Halted 0 ms 0 KB -