Submission #395320

#	Time	Username	Problem	Language	Result	Execution time	Memory
395320		iulia13	Coins (BOI06_coins)	C++14	50 / 100	303 ms	10044 KiB

coins

#include <iostream>

using namespace std;
#define ll long long
struct ura{
    int x, y;
};
ura v[500005];
ura ans;
int main()
{
    ll n, k, s = 0, cnt = 0, nr = 0;
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
    {
        ll c, tip;
        cin >> c >> tip;
        if (c > s && tip == 0) ///rest
        {
            if (ans.x < nr || (ans.x == nr && ans.y > s))
            {
                ans.x = nr;
                ans.y = s;
            }
            while (cnt && v[cnt].y) ///useless
            {
                s -= v[cnt].x;
                cnt--;
            }
            s += c;
            nr++;
        }
        else
        if (c <= s)
        {
            /*a1 + ... + ai >= aj
            a1+.......+ai-1>= aj nu*/
            s -= v[cnt].x;
            if (v[cnt].y == 0)
                nr--;
            cnt--;
            s += c;
            if (tip == 0)
                nr++;
        }
        if (s > k)
            break;
        cnt++;
        v[cnt] = {c, tip};
    }
    if (s <= k)
    {
        if (ans.x < nr || (ans.x == nr && ans.y > s))
        {
            ans.x = nr;
            ans.y = s;
        }
    }
    cout << ans.x << '\n' << k - ans.y;
    return 0;
}

Compilation message (stderr)

coins.cpp: In function 'int main()':
coins.cpp:49:19: warning: narrowing conversion of 'c' from 'long long int' to 'int' [-Wnarrowing]
   49 |         v[cnt] = {c, tip};
      |                   ^
coins.cpp:49:22: warning: narrowing conversion of 'tip' from 'long long int' to 'int' [-Wnarrowing]
   49 |         v[cnt] = {c, tip};
      |                      ^~~

• Subtask 1: 50 / 100