| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 603833 | gagik_2007 | 카니발 티켓 (IOI20_tickets) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "tickets.h"
#include <iostream>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <string>
using namespace std;
#define ff first
#define ss second
typedef long long ll;
typedef long double ld;
const ll INF = 1e18;
ll n, k, m;
vector<ll>mns, mxs, mns_, mxs_;
ll dp[1507][1507];
ll find_answer(vector<ll>a) {
ll ans = INF;
for (int i = 0; i < a.size(); i++) {
ll cur = 0;
for (int j = 0; j < a.size(); j++) {
cur += abs(a[i] - a[j]);
}
ans = min(ans, cur);
}
return ans;
}
ll find_maximum(int k, vector<vector<int>> x) {
n = x.size();
m = x[0].size();
if (m == 1) {
vector<vector<int>>ans;
vector<ll>v;
ans.resize(n);
for (int i = 0; i < n; i++) {
ans[i].resize(1, 0);
v.push_back(x[i][0]);
}
allocate_tickets(ans);
return find_answer(v);
}
if (k == 1) {
mns.push_back(0);
mxs.push_back(0);
for (int i = 0; i < n; i++) {
ll mn = INF, mx = 0;
int mn_ = -1, mx_ = -1;
for (int j = 0; j < m; j++) {
if (x[i][j] < mn) {
mn_ = j;
}
if (x[i][j] > mx) {
mx_ = j;
}
mn = min(mn, x[i][j] * 1ll);
mx = max(mx, x[i][j] * 1ll);
}
mns.push_back(mn);
mxs.push_back(mx);
mns_.push_back(mn_);
mxs_.push_back(mx_);
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= i; j++) {
if (j != 0 && j != i) {
dp[i][j] = max(dp[i - 1][j] + mxs[i], dp[i - 1][j - 1] - mns[i]);
}
else if (j == 0) {
dp[i][j] = dp[i - 1][j] + mxs[i];
}
else {
dp[i][j] = dp[i - 1][j - 1] - mns[i];
}
}
}
string s = "";
int j = n / 2;
for (int i = n; i > 0; i--) {
if (j == i || (j != 0 && dp[i - 1][j - 1] - mns[i] == dp[i][j])) {
s += '0';
j--;
}
else {
s += '1';
}
}
reverse(s.begin(), s.end());
vector<vector<int>>ans;
ans.resize(n);
for (int i = 0; i < n; i++) {
ans[i].resize(m, -1);
}
for (int i = 0; i < n; i++) {
if (s[i] == '0') {
ans[i][mns_[i]] = 0;
}
else {
ans[i][mxs_[i]] = 0;
}
}
allocate_tickets(ans);
return dp[n][n / 2];
}
}
/*
3 1 1 1 2 3
*/