Submission #395323

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
395323	2021-04-28T08:05:05 Z	iulia13	Coins (BOI06_coins)	C++14	90 / 100	302 ms	324 KB

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++;
            cnt++;
        v[cnt] = {c, tip};
        }
        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++;
            cnt++;
        v[cnt] = {c, tip};
        }
        if (s > k)
            break;
    }
    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

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

Subtask #1

90.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	302 ms	276 KB	Output is correct
8	Incorrect	293 ms	204 KB	Output isn't correct
9	Correct	293 ms	276 KB	Output is correct
10	Correct	286 ms	324 KB	Output is correct