oj.uz

Submission #602214

# Submission time Handle Problem Language Result Execution time Memory
602214 2022-07-22T17:22:22 Z gagik_2007 Snowball (JOI21_ho_t2) C++17
33 / 100
 2500 ms 852 KB 
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef ll itn;

#define ff first
#define ss second

string findSum(string str1, string str2)
{
    if (str1.length() > str2.length())
        swap(str1, str2);
    string str = "";
    ll n1 = str1.length(), n2 = str2.length();
    reverse(str1.begin(), str1.end());
    reverse(str2.begin(), str2.end());
    ll carry = 0;
    for (ll i = 0; i < n1; i++)
    {
        ll sum = ((str1[i] - '0') + (str2[i] - '0') + carry);
        str.push_back(sum % 10 + '0');
        carry = sum / 10;
    }
    for (ll i = n1; i < n2; i++)
    {
        ll sum = ((str2[i] - '0') + carry);
        str.push_back(sum % 10 + '0');
        carry = sum / 10;
    }
    if (carry)
        str.push_back(carry + '0');
    reverse(str.begin(), str.end());
    return str;
}
bool isSmaller(string str1, string str2)
{
    ll n1 = str1.length(), n2 = str2.length();
    if (n1 < n2)
        return true;
    if (n2 < n1)
        return false;
    for (ll i = 0; i < n1; i++)
        if (str1[i] < str2[i])
            return true;
        else if (str1[i] > str2[i])
            return false;
    return false;
}
string findDiff(string str1, string str2)
{
    if (isSmaller(str1, str2))
        swap(str1, str2);
    string str = "";
    ll n1 = str1.length(), n2 = str2.length();
    reverse(str1.begin(), str1.end());
    reverse(str2.begin(), str2.end());
    ll carry = 0;
    for (ll i = 0; i < n2; i++) {
        ll sub
            = ((str1[i] - '0') - (str2[i] - '0') - carry);
        if (sub < 0) {
            sub = sub + 10;
            carry = 1;
        }
        else
            carry = 0;
        str.push_back(sub + '0');
    }
    for (ll i = n2; i < n1; i++) {
        ll sub = ((str1[i] - '0') - carry);
        if (sub < 0) {
            sub = sub + 10;
            carry = 1;
        }
        else
            carry = 0;
        str.push_back(sub + '0');
    }
    reverse(str.begin(), str.end());
    return str;
}

ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 32768;
const ll N = 100007;
ll n, m, k;
ll a[1000007];
ll l[1000007];
ll r[1000007];
ll w[1000007];

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        l[i] = a[i];
        r[i] = a[i];
    }
    for (int j = 0; j < k; j++) {
        ll x;
        cin >> x;
        if (x < 0) {
            x = abs(x);
            ll tmp = x - a[0] + l[0];
            w[0] += max(0ll, tmp);
            a[0] -= x;
            l[0] = min(l[0], a[0]);
            for (int i = 1; i < n; i++) {
                ll tmp = x - a[i] + l[i];
                w[i] += max(0ll, min(tmp, l[i] - r[i - 1]));
                a[i] -= x;
                l[i] = min(l[i], a[i]);
            }
        }
        else {
            ll tmp = x - r[0] + a[0];
            w[n - 1] += max(0ll, tmp);
            a[n - 1] += x;
            r[n - 1] = max(r[n - 1], a[n - 1]);
            for (int i = 0; i < n - 1; i++) {
                tmp = x - r[i] + a[i];
                w[i] += max(0ll, min(tmp, l[i + 1] - r[i]));
                a[i] += x;
                r[i] = max(r[i], a[i]);
            }
        }
        /*for (int i = 0; i < n; i++) {
            cout << i << ": " << l[i] << " " << r[i] << " " << a[i] << " " << w[i] << endl;
        }*/
    }
    for (int i = 0; i < n; i++) {
        cout << w[i] << endl;
    }
}

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 13 ms 392 KB Output is correct
5 Correct 13 ms 340 KB Output is correct
6 Correct 16 ms 428 KB Output is correct
7 Correct 12 ms 396 KB Output is correct
8 Correct 13 ms 340 KB Output is correct
9 Correct 12 ms 392 KB Output is correct
10 Correct 12 ms 340 KB Output is correct
11 Correct 12 ms 340 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 14 ms 412 KB Output is correct
16 Correct 13 ms 408 KB Output is correct
17 Correct 13 ms 392 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 12 ms 340 KB Output is correct

Subtask #2
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 13 ms 392 KB Output is correct
5 Correct 13 ms 340 KB Output is correct
6 Correct 16 ms 428 KB Output is correct
7 Correct 12 ms 396 KB Output is correct
8 Correct 13 ms 340 KB Output is correct
9 Correct 12 ms 392 KB Output is correct
10 Correct 12 ms 340 KB Output is correct
11 Correct 12 ms 340 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 14 ms 412 KB Output is correct
16 Correct 13 ms 408 KB Output is correct
17 Correct 13 ms 392 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 12 ms 340 KB Output is correct
20 Correct 82 ms 308 KB Output is correct
21 Correct 80 ms 312 KB Output is correct
22 Correct 146 ms 212 KB Output is correct
23 Correct 911 ms 376 KB Output is correct
24 Execution timed out 2580 ms 852 KB Time limit exceeded
25 Halted 0 ms 0 KB -