Submission #1078080

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1078080	2024-08-27 12:25:25	anango	Carnival Tickets (IOI20_tickets)	C++17	53 / 100	1144 ms	168680 KiB

tickets

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<vector<signed>> intify(vector<vector<int>> res) {
    vector<vector<signed>> ans(res.size(),vector<signed>(res[0].size()));
    for (int i=0; i<res.size(); i++) {
        for (int j=0; j<res[0].size(); j++) {
            ans[i][j] = res[i][j];
        }
    }
    return ans;
}
long long find_maximum(signed k, std::vector<std::vector<signed>> x) {
    //need to fill the grid with + and -
    //exactly k of these in each row
    //such that the total sum of + minus total sum of - is maximised
    //so if we let the possible moves for each row be a set S, each element is {a,b}
    //a is the increase in total sum of + minus total sum of -
    //and b is the total change to the balance (number of + minus number of -)
    //then effectively in each row we need to process these moves in a dp
    //like if we let dp[i][balance] be the maximum answer after doing the first i rows with balance + minus - count
    //the balance can be upto nk/2 = O(n^2), so O(n^3) states and thusforely O(n^4) time complexity
    //passes for 63
    //try optimise to O(n^3)
    //randomise order of rows processed and hope the balance value doesn't become large in the optimal sol?
    //actually quite reasonable
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

tickets.cpp: In function 'std::vector<std::vector<int> > intify(std::vector<std::vector<long long int> >)':
tickets.cpp:9:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |     for (int i=0; i<res.size(); i++) {
      |                   ~^~~~~~~~~~~
tickets.cpp:10:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |         for (int j=0; j<res[0].size(); j++) {
      |                       ~^~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 0 / 14
• Subtask 4: 14 / 14
• Subtask 5: 12 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10