oj.uz

답안 #304555

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
304555 2020-09-21T13:47:39 Z Leonardo_Paes 카니발 티켓 (IOI20_tickets) C++17
27 / 100
 763 ms 77272 KB 
#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1510;
int N, M, mat[2][maxn], nxt[maxn][maxn]; // min e max, 0 e 1
long long dp[maxn][maxn];
long long solve(int row, int qtd){
    if(row == N) return 0;
    if(dp[row][qtd] != -1) return dp[row][qtd];
    if(qtd == 0) dp[row][qtd] = -mat[0][row] + solve(row+1, qtd), nxt[row][qtd] = qtd;
    else if(N-row == qtd) dp[row][qtd] = mat[1][row] + solve(row+1, qtd-1), nxt[row][qtd] = qtd-1;
    else{
        long long caso1 = mat[1][row] + solve(row+1, qtd-1);
        long long caso2 = -mat[0][row] + solve(row+1, qtd);
        if(caso1 > caso2){
            dp[row][qtd] = caso1;
            nxt[row][qtd] = qtd-1;
        }
        else{
            dp[row][qtd] = caso2;
            nxt[row][qtd] = qtd;
        }
    }
    return dp[row][qtd];
}
long long find_maximum(int k, vector<vector<int>> x) {
	N = x.size(), M = x[0].size();
	vector<vector<int>> answer;
	for(int i=0; i<N; i++){
		vector<int> row(M);
		for(int j=0; j<M; j++) row[j] = -1;
		answer.push_back(row);
		mat[0][i] = x[i][0];
		mat[1][i] = x[i][M-1];
	}
	memset(dp, -1, sizeof dp);
	long long ans = solve(0, N/2);
	int qtd = N/2;
	for(int r=0; r<N; r++){
        if(nxt[r][qtd] == qtd) answer[r][0] = 0;
        else{
            answer[r][M-1] = 0;
            qtd--;
        }
	}
	allocate_tickets(answer);
	return ans;
	/*
4 2 1
5 9
1 4
3 6
2 7
	*/
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 18176 KB Output is correct
2 Correct 12 ms 18304 KB Output is correct
3 Correct 11 ms 18176 KB Output is correct
4 Correct 11 ms 18560 KB Output is correct
5 Correct 12 ms 19584 KB Output is correct
6 Correct 38 ms 26616 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 18176 KB Output is correct
2 Correct 11 ms 18176 KB Output is correct
3 Correct 11 ms 18176 KB Output is correct
4 Correct 13 ms 18688 KB Output is correct
5 Correct 46 ms 21624 KB Output is correct
6 Correct 763 ms 77272 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 18176 KB There is no ticket of color 0 on day 1
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 18176 KB There is no ticket of color 0 on day 1
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 18176 KB There is no ticket of color 0 on day 1
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 18176 KB There is no ticket of color 0 on day 1
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 18176 KB Output is correct
2 Correct 12 ms 18304 KB Output is correct
3 Correct 11 ms 18176 KB Output is correct
4 Correct 11 ms 18560 KB Output is correct
5 Correct 12 ms 19584 KB Output is correct
6 Correct 38 ms 26616 KB Output is correct
7 Correct 12 ms 18176 KB Output is correct
8 Correct 11 ms 18176 KB Output is correct
9 Correct 11 ms 18176 KB Output is correct
10 Correct 13 ms 18688 KB Output is correct
11 Correct 46 ms 21624 KB Output is correct
12 Correct 763 ms 77272 KB Output is correct
13 Incorrect 11 ms 18176 KB There is no ticket of color 0 on day 1
14 Halted 0 ms 0 KB -