codeforce 1300
COFO::1285B Just Eat It!
cofo problem
COFO::1285B Just Eat It!
Problem
- level : 1300
- tag : dp, greedy, implementation
- TIME
- to understand :
- to algorithm : fail
- to code :
- to debug :
- understaing edit : 10
- 1300문제를 1500문제만큼 복잡하게 고민했습니다.
- 명료하게 캐치해내는 능력이 부족한 것 같습니다.
- 구간에 대한 문제는 suffix, prefix를 힌트로 사용할 수 있다는 점을 기억해야겠습니다.
Point
- n이 주어집니다.
- n개의 원소로 이루어진 배열 a 가 주어집니다.
- Yasser는 n개 전체를 합한 합을 가지고 있습니다.
- Adel은 구간 [l, r]에 대해 배열 a의 합을 만들 수 있습니다.
- 단 해당 구간은 전체 배열인 경우를 제외합니다.
- 이때, Yasser이 항상 어떤 구간합보다 큰 경우 Yes 를 출력합니다.
Design
- 연속으로 플러스인 구간의 합, 연속으로 마이너스인 구간의 합, … 을 구해서, 답을 찾으려 했지만 실패했습니다.
- prefix or suffix 에 대해서 연속합이 양이 아닌 경우가 존재한다면, No를 출력합니다.
- 구간의 합이 0이하인 경우 해당 구간을 제외해도 되기 떄문에, 해당 구간을 제외한 합과 전체 구간의 합이 같거나 그 이하이기때문입니다.
- 혹은 다음과 같이 걸러내도 됩니다.
- prefix or suffix의 구간합이 전체 합 이상이 되는 경우
- 결국, 합은 더할수록 점점 커집니다.
- 따라서 a 배열의 양쪽 끝에 마이너스가 있는 경우 해당 값들을 제외한 합만이 전체 합에 견주어볼만합니다.
- 하지만 중간에 큰 마이너스가 있고 그 양쪽에 작은 양수가 있는 경우도 있으니, 중간중간 더하며 계속 체크해주어야하죠
Complexitya
- O(N)
Code
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n;
vector <int> a;
bool solve(){
cin >> n;
a.resize(n);
for(auto &i : a) cin >> i;
ll sum = 0;
for(int i = 0 ; i < n ; i++){
sum += a[i];
if(sum <= 0) return 0;
}
sum = 0;
for(int i = n - 1 ; i >= 0 ; i--){
sum += a[i];
if(sum <= 0) return 0;
}
return 1;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
while(T--){
if(solve()) cout << "YES\n";
else cout << "NO\n";
}
}
#include<iostream>
#include<vector>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define r_rep(i, a, b) for(int i=(a); i >(b); i--)
typedef long long ll;
using namespace std;
int n;
vector<ll> v;
bool solve(){
v.clear();
cin >> n;
v.resize(n);
ll s = 0;
rep(i, 0, n){
cin >> v[i];
s += v[i];
}
ll sum = 0;
rep(i, 0, n-1){
sum += v[i];
if(sum >= s) return false;
}
sum = 0;
r_rep(i, n-1, 0){
sum += v[i];
if(sum >= s) return false;
}
return true;
}
int main(){
// freopen("input.txt", "r", stdin);
int tc; cin >> tc;
while(tc--) if(solve()) cout << "YES\n"; else cout << "NO\n";
return 0;
}