oj.uz

Submission #231377

# Submission time Handle Problem Language Result Execution time Memory
231377 2020-05-13T13:11:03 Z SSYernar Bigger segments (IZhO19_segments) C++14
0 / 100
 5 ms 384 KB 
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
//using namespace __gnu_pbds;
 
void err(istream_iterator<string> it) {cout << '\n';}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr << "[" << *it << " = " << a << "] ";
    err(++it, args...);
}
 
#define F first
#define S second
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pf push_front
#define db double
#define ld long double
#define ppb pop_back
#define ppf pop_front
#define br cout << '\n'
#define pll pair<long long, long long>
#define pipii pair<int, pii>
#define ppiii pair<pii, int>
#define piipii pair<pii, pii>
#define here cout << "HERE\n"
#define all(x) (x).begin(),(x).end()
#define __ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define watch(x) cout << (#x) << " is " << (x) << endl
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define TEST int TT; cin >> TT; for(int T = 1; T <= TT; T++)
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
//#define int ll
#define pii pair<int, int>
 
const int inf = 2e9 + 7;
const ll INF = 3e18 + 7;
int mod = 1e9 + 7;
ll MOD = 1e15 + 7;
 
const bool multiple_tests = 0;
const int N = 3e5 + 7;


void solve() {
    int n;
    cin >> n;
    int a[n + 1];
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    ll cur = 0;
    int ans = 1;
    for (int i = 1; i <= n; i++) {
        cur += a[i];
        ll aim = cur;
        ll sum = 0;
        int cnt = 1;
        for (int j = i + 1; j <= n; j++) {
            sum += a[j];
            if (sum >= aim) {
                aim = sum;
                sum = 0;
                cnt++;
            }
        }
        ans = max(ans, cnt);
    }
    cout << ans;
}
 
// What we can do:
//   -
 
 
// IF CODE IS TOO LONG LOOK FOR ANOTHER IDEA
// if TL:
//    - Use io scan and print
//    - Do we really need to visit all states?
// dp with input parameters
// ...
 
 
 
 
 
signed main() { __
//    freopen("lcm.in", "r", stdin);
//    freopen("lcm.out", "w", stdout);
    int TT = 1;
    if (multiple_tests) cin >> TT;
    for (int T = 1; T <= TT; T++) {
//        cout << "Test Case #" << T << ": ";
        solve();
        cout << '\n';
    }
    
    #ifndef AMIR_MAL
      cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    #endif
    return 0;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Incorrect 5 ms 384 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Incorrect 5 ms 384 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Incorrect 5 ms 384 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Incorrect 5 ms 384 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Incorrect 5 ms 384 KB Output isn't correct
10 Halted 0 ms 0 KB -