Submission #1090022

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1090022	2024-09-17 14:52:21	onlk97	Carnival Tickets (IOI20_tickets)	C++14	67 / 100	556 ms	114588 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;
long long dp[300][10000],bac[300][10000],ps[100][100],bps[100][100];
long long find_maximum(int k,vector <vector <int> > x){
    int n=x.size(),m=x[0].size();
    vector <vector <int> > op(n,vector <int>(m,-1));
    int chkmx=0;
    for (int i=0; i<n; i++) for (int j=0; j<m; j++) chkmx=max(chkmx,x[i][j]);
    long long ans=0;
    if (k==1){
        int idxmn[n],idxmx[n];
        for (int i=0; i<n; i++){
            idxmn[i]=min_element(x[i].begin(),x[i].end())-x[i].begin();
            idxmx[i]=max_element(x[i].begin(),x[i].end())-x[i].begin();
        }
        long long dp[n+1][n+1],bac[n+1][n+1];
        for (int i=0; i<=n; i++){
            for (int j=0; j<=n; j++) dp[i][j]=-1e18;
        }
        dp[0][0]=0;
        for (int i=0; i<n; i++){
            for (int j=0; j<=n/2; j++){
                if (dp[i][j]-x[i][idxmn[i]]>=dp[i+1][j]){
                    dp[i+1][j]=dp[i][j]-x[i][idxmn[i]];
                    bac[i+1][j]=0;
                }
                if (dp[i][j]+x[i][idxmx[i]]>=dp[i+1][j+1]){
                    dp[i+1][j+1]=dp[i][j]+x[i][idxmx[i]];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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