| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1290631 | amodi | Xylophone (JOI18_xylophone) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#include "xylophone.h"
#define int long long
static int A[5000];
void solve(int n) {
vector<array<int,2>>fark(n+1);
fark[n-1][0]=query(n-1,n);
for(int i=1;i<n-1;i++) {
fark[i][0]=query(i,i+1);
fark[i][1]=query(i,i+2);
}
vector<bool>cs(n+1);
//ilk yön +
cs[1]=1;
int toplam=0;
int mx=0;
int mn=0;
int mxi=1;
int mni=1;
for(int i=1;i<n-1;i++){
if(fark[i][1]==fark[i+1][0]+fark[i][0])cs[i+1]=cs[i];
else cs[i+1]=(!cs[i]);
}
for(int i=1;i<=n-1;i++){
if(cs[i])toplam+=fark[i][0];
else toplam +=0-fark[i][0];
if(mx<toplam){
mx=toplam;
mxi=i+1;
}
if(mn<toplam){
mn=toplam;
mni=i+1;
}
}
if(mni<mxi){
int ansid=n-mx;
answer(1,ansid);
for(int i=2;i<=n;i++){
if(!cs[i])ansid-=fark[i-1][0];
else ansid+=fark[i-1][0];
answer(i,ansid);
}
}
//ilk yön -
else{
cs[1]=0;
//int toplam=0;
mx=0;
mn=0;
mxi=1;
mni=1;
toplam=0;
for(int i=1;i<n-1;i++){
if(fark[i][1]==fark[i+1][0]+fark[i][0])cs[i+1]=cs[i];
else cs[i+1]=(!cs[i]);
}
for(int i=1;i<=n-1;i++){
if(cs[i])toplam+=fark[i][0];
else toplam +=0-fark[i][0];
if(mx<toplam){
mx=toplam;
mxi=i+1;
}
if(mn<toplam){
mn=toplam;
mni=i+1;
}
}
int ansid=n-mx;
answer(1,ansid);
for(int i=2;i<=n;i++){
if(!cs[i])ansid-=fark[i-1][0];
else ansid+=fark[i-1][0];
answer(i,ansid);
}
}
}