oj.uz

Submission #300470

# Submission time Handle Problem Language Result Execution time Memory
300470 2020-09-17T07:42:44 Z kevlee Carnival Tickets (IOI20_tickets) C++17
27 / 100
 941 ms 79212 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) {
      sum += x[i][j];
      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];
      sum += tmp.fi;
      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] != -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 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 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 5 ms 2688 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 3 ms 640 KB Output is correct
5 Correct 32 ms 2816 KB Output is correct
6 Correct 887 ms 53496 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 3 ms 768 KB Output is correct
5 Correct 39 ms 4096 KB Output is correct
6 Correct 857 ms 78296 KB Output is correct
7 Correct 941 ms 79212 KB Output is correct
8 Incorrect 4 ms 1024 KB Contestant returned 4739 while correct return value is 4989.
9 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Contestant returned 11 while correct return value is 13.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Contestant returned 11 while correct return value is 13.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Contestant returned 11 while correct return value is 13.
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 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 5 ms 2688 KB Output is correct
7 Correct 0 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 3 ms 640 KB Output is correct
11 Correct 32 ms 2816 KB Output is correct
12 Correct 887 ms 53496 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 3 ms 768 KB Output is correct
17 Correct 39 ms 4096 KB Output is correct
18 Correct 857 ms 78296 KB Output is correct
19 Correct 941 ms 79212 KB Output is correct
20 Incorrect 4 ms 1024 KB Contestant returned 4739 while correct return value is 4989.
21 Halted 0 ms 0 KB -