akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>; using pll = pair<ll, ll>;

#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i < (n); i++)

template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}
template<class F, class S> istream& operator >> (istream& s, pair<F, S>& p)
{ s >> p.first >> p.second; return s;}

int main()
{
    int N; cin >> N;
    vector<int> A(N);
    map<int, ll> m;
    ll sum = 0;
    rep(i, N) {
        int A; cin >> A;
        m[A]++;
        sum += A;
    }

    int Q; cin >> Q;
    rep(i, Q) {
        int B, C; cin >> B >> C;
        ll cnt = m[B];
        if (cnt > 0) {
            ll add = (C-B) * cnt;
            sum += add;
            m[B] -= cnt;
            m[C] += cnt;
        }
        cout << sum << endl;
    }
}


Measured memory_bytes: 9288
#pragma GCC optimize("Ofast,inline,unroll-loops,fast-math")
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <sstream>
#include <bitset>
#include <memory>
#include <string>
#include <vector>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <deque>
#include <algorithm>
#include <random>
#include <iomanip>
using namespace std;


int main(int argc, char *argv[]) {
	int n;
	cin >> n;
	string s, t;
	cin >> s >> t;
	for (int i = 0; i < n; i++)
		cout << s[i] << t[i];
	cout << endl;


}









Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;

const int MAX = 999984;
bool isPrime[MAX];

void createIsPrime() {
    fill_n(isPrime, MAX, true);
    isPrime[0] = false;
    isPrime[1] = false;
    for (int i = 4; i < MAX; i += 2) {
        isPrime[i] = false;
    }
    for (int i = 3; i * i <= MAX; i += 2) {
        if (isPrime[i]) {
            for (int j = i * 2; j < MAX; j += i) {
                isPrime[j] = false;
            }
        }
    }
}

int main() {
    createIsPrime();
    while (true) {
        int n;
        cin >> n;
        if (n == 0) {
            break;
        }
        int bill = 0;
        while (n--) {
            int p, m;
            cin >> p >> m;
            int prime = 0, start = p - m;
            if ((p - m) % 2 == 0) {
                start++;
            }
            if (p - m <= 2) {
                bill++;
            }
            for (int i = max(start, 3), end = min(p + m, MAX - 1); i <= end; i += 2) {
                if (isPrime[i]) {
                    prime++;
                }
            }
            if (prime > 0) {
                bill += prime - 1;
            } else {
                bill--;
            }
        }
        cout << bill << endl;
    }
}

Measured memory_bytes: 1844
#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using P = pair<ll,ll>;
#define REP(i,n) for(ll i = 0;i < (ll)n;i++)
#define REPD(i,n) for(ll i = (ll)n - 1;i >= 0;i--)
#define ALL(x) (x).begin(),(x).end()
#define FILL(n,first_dimension_size,value) fill((ll*)n,(ll*)(n+first_dimension_size),value)
#define INF (1 << 29)
#define MOD 1000000007
//int dx[4] = {1,0,0,-1};
//int dy[4] = {0,1,-1,0};


int main(){
  
  ll a,b;
  cin >> a >> b;
  if((a + b)%2)cout << "IMPOSSIBLE";
  else cout << (a + b)/2;


  return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
import sys


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    pairs = []
    for i in range(N):
        pairs.append((A[i], B[i]))
    pairs.sort(key=lambda x: x[0])
    ret = 0
    for p, num in pairs:
        if M <= num:
            ret += p * M
            break
        else:
            ret += p * num
            M -= num
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]" 
    B = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)

if __name__ == '__main__':
    main()


Measured memory_bytes: 19824
using System;

namespace Kyopuro
{
    class Program
    {
        static void Main(string[] args)
        {


            string[] str = Console.ReadLine().Split(' ');
            string[] strr = Console.ReadLine().Split(' ');

            int i;

            int N = int.Parse(str[0]);
            int K = int.Parse(str[1]);

            double[] num = new double[N+1];

            int max = 0;


            //累積和の生成
            for (i = 0; i <= N; i++)
            {
                if (i == 0)
                {
                    num[0] = 0;
                }
                else
                {
                    num[i] = (double)(int.Parse(strr[i-1]) + 1) / 2 + num[i-1];
                }
            }

            max = K;
            //最も大きい部分を取り出したい
            for (i = K; i <= N; i++)
            {
                if (num[i]-num[i-K] > num[max]- num[max-K])
                {
                    max = i;
                }
            }

            if(max == K - 1)
            {

                Console.WriteLine(string.Format("{0:0.000000000000}", num[max]));
            }
            else
            {
                Console.WriteLine(string.Format("{0:0.000000000000}", num[max] - num[max - K]));
            }




        }
    }
}

Measured memory_bytes: 29020
#if 0
?????¨?????????2h
bfs??????????????¢?´¢???????????°????????§?????????
????????????????´????????????\?????????????????????????????¨????????????????????£??????????????????queue?????????????????¢?????????
main?????§???????????§?§£????????£??\?????????to??£??\??????????????????????????£??????
????????????????????????????????????????????¨?????´?????????
#endif

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n, D[100];
int G[100][100];
void bfs(int src){
	queue<int> q;
	q.push(src);
	D[src]=0;
	while(!q.empty()){
		int cur=q.front();
		q.pop();
		for(int dst=0;dst<n;dst++){
			if(G[cur][dst]==1&&D[dst]==-1){
				D[dst]=D[cur]+1;
				q.push(dst);
			}
		}
	}
};

int main()
{
	vector<int> v[110];
	cin>>n;
	for(int i=0;i<n;i++){
		int u,k;
		cin>>u>>k;
		for(int j=0;j<k;j++){
			int tmp;
			cin>>tmp;
			v[u].push_back(tmp);
		}
	}
	for(int i=0;i<100;i++){
		D[i]=-1;
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			G[i][j]=0;
		}
	}
	for(int i=1;i<n+1;i++){
		for(int j=0;j<v[i].size();j++){
			G[i-1][v[i][j]-1]=1; //
		}
	}
	bfs(0);
	for(int i=0;i<n;i++){
		cout<<(i+1)<<' '<<D[i]<<endl;
	}
}

Measured memory_bytes: 3176
#include <bits/stdc++.h>
using namespace std;
using PP = pair<int, int>;

const long inf = 1e18;
int n;
long a[200000];
map<PP, long> dp;
map<PP, long> dq;

long g(int i, int j);
long f(int i, int j) {
  if (i == 0 && j == 0) return 0;
  if (i == 0) return -inf;
  if (2 * j > i + 8) return -inf;
  if (2 * j < i - 8) return -inf;
  if (dp.count(PP(i, j))) return dp[PP(i, j)];
  long ans = a[i - 1] + g(i - 1, j - 1);
  return dp[PP(i, j)] = ans;
}

long g(int i, int j) {
  if (i == 0 && j == 0) return 0;
  if (i == 0) return -inf;
  if (2 * j > i + 8) return -inf;
  if (2 * j < i - 8) return -inf;
  if (dq.count(PP(i, j))) return dq[PP(i, j)];
  long ans = max(f(i - 1, j), g(i - 1, j));
  return dq[PP(i, j)] = ans;
}

int main() {
  cin >> n;
  for (int i = 0; i < n; ++i) cin >> a[i];
  cout << max(f(n, n / 2), g(n, n / 2)) << endl;
}

Measured memory_bytes: 156736
using System.Collections.Generic;
using static System.Console;

class Atcoder
{
    public static void Main()
    {
        var d = new Dictionary<string, string>()
        {{"A", "T"}, {"T", "A"}, {"C", "G"}, {"G", "C"}};
        WriteLine(d[ReadLine()]);
    }
}


Measured memory_bytes: 13152
import sys
input = sys.stdin.readline


def f(sc, target):
    for s, c in sc:
        if int(target[s-1]) != c:
            return False
    return True


def main():
    n, m = map(int, input().split())
    sc = []
    for _ in range(m):
        sc.append(tuple(map(int, input().split())))
    for i in range(1000):
        if len(str(i)) != n:
            continue
        target = str(i)
        if f(sc, target):
            print(target)
            return
    print(-1)


if __name__ == "__main__":
    main()


Measured memory_bytes: 38256
#include <bits/stdc++.h>

#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define SORTASC(c) sort((c).begin(), (c).end())
#define SORTDESC(c, t) sort((c).begin(), (c).end(), std::greater<t>());
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define VMAX(a) *max_element(ALL(a))
#define VMIN(a) *min_element(ALL(a))
#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
                      << " " << __FILE__ << endl;

const double PI = acos(-1.0);

using ll = long long;
using namespace std;

int main()
{
    ll n, k;
    ll ans = 1;

    cin >> n >> k;

    while(n>=k){
        n/=k;
        ans++;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main{
  public static void main(String[]args){

    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    String s = sc.next();

    if(a>=2800 && a<5000){
      if(a>=3200){
        System.out.println(s);
      }
      if(a<3200){
        System.out.println("red");
      }
    }

  }
}


Measured memory_bytes: 23508
t = int(input()) 
for t in range(t):
    N,K = map(int, input().strip().split(" "))
    X = list(map(int,input().strip().split(" ")))
    L = [X[i+1] - X[i] for i in range(0,N-1)]
    L.sort()
    s = 0
    for i in range(0,N-K):
        s = s + L[i]
    print(s)


Measured memory_bytes: 21764
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <utility>
#include <tuple>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cmath>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int main() {
  int n;
  cin >> n;
  vector<pair<int, int>> a(n);
  rep(i, n) cin >> a[i].first >> a[i].second;
  sort(a.begin(), a.end());
  cout << a.back().first+a.back().second << endl;
  return 0;
}

Measured memory_bytes: 1024
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric, std.container;

void main()
{
    auto nm = readln.split.to!(int[]);
    auto N = nm[0];
    auto M = nm[1];
    int[][] aa;
    foreach (i; 0..N) aa ~= readln.split.map!(a => a.to!int-1).array;
    auto ss = new bool[](M);
    ss[] = true;
    auto r = N+1;
    foreach (_; 0..M) {
        auto ps = new int[](M);
        foreach (i; 0..N) {
            foreach (s; aa[i]) if (ss[s]) {
                ps[s] += 1;
                break;
            }
        }
        int max_p;
        size_t k;
        foreach (i, p; ps) if (p > max_p) {
            max_p = p;
            k = i;
        }
        r = min(r, max_p);
        ss[k] = false;
    }
    writeln(r);
}

Measured memory_bytes: 4940
#include <bits/stdc++.h>
#define pb push_back
#define sz(a) int(a.size())
#define re return
using namespace std;
int main()
{
	int n,k;
	cin>>n>>k;
	if (n<10)  k=k+ 100* (10- n);
	cout<<k;
	re 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
using ll = long long;
using pll = pair<ll, ll>;
#define all(x) (x).begin(), (x).end()
#define call(x) (x).cbegin(), (x).cend()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define sz(x) ((x).size())
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define rep(i, a, b) for(ll i = ll(a); i < ll(b); i++)
const double PI = acos(-1);
const int mod = 1e9+7;
const long long INF = (1LL << 60);
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
ll gcd(ll a,ll b){return b ? gcd(b,a%b) : a;}
ll lcm(ll a,ll b){return a / gcd(a,b) * b;}
ll stringcount(string s, char c){return count(s.cbegin(), s.cend(), c);}
bool isInteger(double x){return floor(x) == x;}
ll ceil(ll a, ll b){return ((a)+(b)-1)/b;}
template<class T> inline bool chmax(T &a, const T &b){ if(a < b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b){ if(a > b){ a=b; return 1; } return 0; }

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);

  string s;
  cin >> s;

  map<string, string> mp;
  mp["Sunny"] = "Cloudy";
  mp["Cloudy"] = "Rainy";
  mp["Rainy"] = "Sunny";
  cout << mp[s] << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define Would
#define you
#define please

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;

	int a[101] = {};

	rep(i, N) {
		int d;
		cin >> d;
		a[d] = 1;
	}
	int kotae = 0;
	rep1(i, 100) {
		kotae += a[i];
	}

	co(kotae);

	Would you please return 0;
}

Measured memory_bytes: 256
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
M = 10 ** 6

B = Counter(A)
Key = list(B.keys())
Key.sort()

table = [1] * (M + 1)
cnt = 0
for k in Key:
    if B[k] == 1:
        if table[k] == 1:
            cnt += 1
    for i in range(M):
        if k * i > M:
            break
        else:
            table[k * i] = 0

print(cnt)


Measured memory_bytes: 118912
def main():
    N = int(input())
    B = [int(i) for i in input().split()]
    ans = []
    while B:
        for i in range(len(B))[::-1]:
            if B[i] == i+1:
                ans.append(B[i])
                del B[i]
                break
        else:
            return print(-1)
    print(*ans[::-1], sep="\n")


if __name__ == '__main__':
    main()


Measured memory_bytes: 38512
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <complex>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#define debug(x) cerr << #x << " = " << (x) << endl;


#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 100010

bool solve(){
  int M,T,P,R;
  int score[50] = {}, penalty[50] = {};
  int subc[50][15] = {};
  
  scanf("%d%d%d%d",&M,&T,&P,&R);
  if(M == 0) return false;

  for(int i=0;i<R;i++){
    int m,t,p,j;

    scanf("%d%d%d%d",&m,&t,&p,&j);
    t--;
    
    if(j == 0){ //AC
      score[t] ++;
      penalty[t] += subc[t][p] * 20 + m;
    }else{
      subc[t][p]++;
    }
  }

  vector<pair<pair<int,int>, int > > standings;
  
  for(int i=0;i<T;i++){
    standings.push_back({{score[i], -penalty[i]},i+1});
  }

  sort(standings.begin(), standings.end(),greater<pair<pair<int,int>,int > >());

  for(int i=0;i<T;i++){
    printf("%d",standings[i].second);
    
    if(i < T-1){
      if(standings[i].first == standings[i+1].first){
        printf("=");
      }else{
        printf(",");
      }
    }else{
      printf("\n");
    }
    
  }

  return true;
}

int main(){

  while(solve());
  
  return 0;
}

Measured memory_bytes: 3220
#include <bits/stdc++.h>
using namespace std;
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
typedef pair<int, int> P;
typedef pair<int64_t, int64_t> Pll;
  
int main() {
    string O, E;
    cin >> O >> E;
    for (int i = 0; i < E.size(); i++) {
        cout << O.at(i) << E.at(i);
    }
    if (E.size() < O.size()) {
        cout << O.at(E.size());
    }
    cout << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define pb push_back
using namespace std;
typedef long long ll;

int main(){
  int n;
  cin>>n;
  vector<int> a(n);
  rep(i,n) cin>>a[i];
  
  if(a[0]!=0){
    cout<<-1<<endl;
    return 0;
  }
  ll res=0;
  rep(i,n-1){
    if(a[i+1]==a[i]+1) res++;
    else if(a[i+1]<=a[i]) res+=a[i+1];
    else{
      cout<<-1<<endl;
      return 0;
    }
  }
  cout<<res<<endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
#define pb push_back
#define sz(i) (int)(i.size())
#define F first
#define S second
#define L long double
#define P pair<int, int>
const int inf = 0x3f3f3f3f3f3f3f3LL;
const int mod = (int)1e9 + 7;
using namespace std;
#if LOCAL
#include "../../tr.h"
#else
#define tr(...)
#define endl '\n'
#endif
template<class T> void smin(T& a, T val) {if (a > val) a = val;}template<class T> void smax(T& a, T val) {if (a < val) a = val;}
const int N = 5*(int)1e5 + 10;

int n, a[N], k, x;
int32_t main(){_

   cin>>k>>x;

   vector<int> v;

   v.pb(x);

   for (int i = x-1; i >= x-k+1; --i)
   {
      v.pb(i);
   }


   for (int i = x+1; i <= x+k-1; ++i)
   {
      v.pb(i);
   }
   
   sort(v.begin(), v.end());

   for(auto i: v)
      cout<<i<<' ';

   return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {

    public static void main(String args[]) {

        // 入力
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int m = Integer.parseInt(sc.next());
        Integer[] a = new Integer[n];
        Arrays.setAll(a, i -> Integer.parseInt(sc.next()));
        sc.close();

        // 主処理
        int sum = Arrays.stream(a).mapToInt(i -> i).sum();

        Arrays.sort(a, Collections.reverseOrder());
        double target = a[m - 1];

        boolean judge = (double) sum / (4.0 * m) <= target;
        String result = judge ? "Yes" : "No";

        // 出力
        System.out.println(result);
    }
}


Measured memory_bytes: 26964
import static java.lang.Math.toRadians;

import java.awt.geom.AffineTransform;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
	Scanner in = new Scanner(System.in);
	AffineTransform affin = new AffineTransform();
	while (in.hasNext()) {
		String[] input = in.next().split(",");
		int length = Integer.parseInt(input[0]);
		double radian = toRadians(-Double.parseDouble(input[1]));
		if (length != 0 || radian != 0) {
			affin.translate(0, length);
			affin.rotate(radian, 0, 0);
		} else {
			System.out.println((int) affin.getTranslateX());
			System.out.println((int) affin.getTranslateY());
			affin.setToIdentity();
		}
	}
}
}

Measured memory_bytes: 12000
using System;

class Program
{
    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());

        double d = 100000;
        for (int i = 0; i < n; i++)
        {
            d = Math.Ceiling(d * 1.05 / 1000) * 1000;
        }

        Console.WriteLine(d);
    }
}

Measured memory_bytes: 5624
#include <stdio.h>
#define MAX 2000000

int A[MAX + 1], H;

void maxHeapify(int i){
  int l, r, largest, a;
  
  l = i * 2;
  r = i * 2 + 1;    
  // ????????????????????????????????§???????????§????????????????????¶
  if(l <= H && A[l] > A[i])
    largest = l;
  else 
    largest = i;

  if(r <= H && A[r] > A[largest])
    largest = r;
  
  // i ???????????????????????§????????´???
  if(largest != i){
    a = A[i];
    A[i] =  A[largest];
    A[largest] = a;
    maxHeapify(largest);  // ?????°??????????????????
  }
}

int main(){
  int i;
  
  scanf("%d", &H); 

  for(i = 1; i <= H; i++) scanf("%d", &A[i]);
  for(i = H / 2; i >= 1; i--) maxHeapify(i);
  for(i = 1; i <= H; i++) printf(" %d", A[i]);
  printf("\n");
  
  return 0;
}

Measured memory_bytes: 2552
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
using namespace std;

int main() {
	int n, k;
	cin >> n >> k;
	ll r, s, p;
	cin >> r >> s >> p;
	string t;
	cin >> t;
	vector<bool> dasuka(n, false);
	ll ans = 0;
	rep(i, k) {
		dasuka[i] = true;
		if (t[i] == 'r') ans += p;
		else if (t[i] == 's') ans += r;
		else ans += s;

	}

	for (int i = k; i < n; i++) {
		if (t[i - k] == t[i] && dasuka[i - k] == true) continue;
		else {
			if (t[i] == 'r') ans += p;
			else if (t[i] == 's') ans += r;
			else ans += s;
			dasuka[i] = true;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 512
n, p = map(int, raw_input().split())
a = map(int, raw_input().split())
t = [1, 0]
for x in a:
    x %= 2
    t = [t[0] + t[1], t[0] + t[1]] if x else [t[0] * 2, t[1] * 2]
print t[p]


Measured memory_bytes: 2572
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;

const ll INF64 = 1LL << 60;
const int INF32 = 1 << 29;
const int MOD = 1000000007;
//const int MOD = 998244353;

// Lib
//

int main(){
#ifdef MYLOCAL
    ifstream in("input.txt");
    cin.rdbuf(in.rdbuf());
#endif
    ll R, G, B, N;
    cin >> R >> G >> B >> N;
    ll res = 0;
    for (ll r = 0; r <= N/R; ++r) {
        for (ll g = 0; g <= N/G; ++g) {
            if (r * R + g * G > N) continue;
            ll rem = N - r*R - g*G;
            if (rem % B != 0) continue;
            ++res;
        }
    }
    cout << res << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  cin >> N;
  int a[N];
  for(int i=0;i<N;i++)cin >> a[i];
  int ans=1000000000;
  for(int i=-100;i<101;i++){
    int sum=0;
    for(int j=0;j<N;j++){
      sum+=(a[j]-i)*(a[j]-i);
    }
    if(sum<ans)ans=sum;
  }
  cout << ans;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>
#include <string>

using namespace std;
using ll = long long;

ll K, A, B;

void input() {
    cin >> K >> A >> B;
}

void solve() {
    ll ans = 1;
    if (B - A > 1) {
        ans = A;
        ll k = K - A + 1;
        ll times = k / 2;
        ans += times * (B - A);
        if (k % 2)
            ans++;
    } else {
        ans = 1 + K;
    }
    cout << ans << endl;
}

int main() {
    input();
    
    solve();
    
    return 0;
}



Measured memory_bytes: 888
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

vector<char> group_arr[100005];
char T[100005];
int N, K, R, S, P;
//string T;
int dp[100005][3];
#define ROCK 0
#define SCISSOR 1
#define PAPER 2

int main() {
#ifdef WIN32
	//freopen("input.txt", "r", stdin);
#endif
	//get input
	scanf("%d%d%d%d%d%s", &N, &K, &R, &S, &P, T);
	//cin >> N >> K >> R >> S >> P >> T;

	//grouping
	for (int i = 0; i < K; i++) {
		group_arr[i].reserve(N);
		for (int idx = i; idx < N; idx += K) {
			group_arr[i].push_back(T[idx]);
		}
	}
	ll ans = 0;
	for (int idx = 0; idx < K; idx++) {
		for (register int i = 1; i <= group_arr[idx].size(); i++) {
			char enemy = group_arr[idx][i - 1];
			if (enemy == 'r') {
				dp[i][PAPER] = max(dp[i - 1][ROCK], dp[i - 1][SCISSOR]) + P;
				dp[i][ROCK] = max(dp[i - 1][PAPER], dp[i - 1][SCISSOR]);
				dp[i][SCISSOR] = max(dp[i - 1][ROCK], dp[i - 1][PAPER]);
			}
			else if (enemy == 's') {
				dp[i][ROCK] = max(dp[i - 1][SCISSOR], dp[i - 1][PAPER]) + R;
				dp[i][PAPER] = max(dp[i - 1][ROCK], dp[i - 1][SCISSOR]);
				dp[i][SCISSOR] = max(dp[i - 1][ROCK], dp[i - 1][PAPER]);
			}
			else if (enemy == 'p') {
				dp[i][SCISSOR] = max(dp[i - 1][ROCK], dp[i - 1][PAPER]) + S;
				dp[i][ROCK] = max(dp[i - 1][SCISSOR], dp[i - 1][PAPER]);
				dp[i][PAPER] = max(dp[i - 1][ROCK], dp[i - 1][SCISSOR]);
			}
		}
		int last = group_arr[idx].size();
		ans += max(dp[last][0], max(dp[last][1], dp[last][2]));
	}
	printf("%lld\n", ans);
	//cout << ans << endl;

	return 0;
}

Measured memory_bytes: 356608
from heapq import heappop,heappush,heapify
n,m=map(int,input().split())
A=[-i for i in list(map(int,input().split()))]
heapify(A)
for i in range(m):
	a=heappop(A)
	heappush(A,-(-a//2))
print(-sum(A))

Measured memory_bytes: 14180
{
  const main = (input: string) => {
    const r = reader(input)
    const [a, b] = r.ns()

    if (!(0 <= a && a <= 9 && 0 <= b && b <= 9)) {
      console.log(-1)
      return
    }
    console.log(a * b)
  }

  const reader = (str: string) => {
    const lines = str.trim().split('\n')
    const s = () => lines.shift() || ''
    const n = () => Number(s())

    const ss = () => s().split(' ')
    const ns = () => ss().map(Number)
    const nls = () => lines.map(Number)

    return { lines, s, n, ss, ns, nls }
  }

  const getInput = () => require('fs').readFileSync('/dev/stdin', 'utf8')

  main(getInput())
}


Measured memory_bytes: 7756
#include "bits/stdc++.h"

using namespace std;

void Task() {
      int n;
      cin >> n;
      vector <int> vec(n + 1);
      vector <int> fre(n + 1);
      for (int i = 1; i <= n; i++) {
            cin >> vec[i];
            fre[ vec[i] ]++;
      }
      long long ans = 0;
      for (int i = 1; i <= n; i++) {
            long long num = fre[i];
            long long choice = num * (num - 1) / 2;
            ans += choice;
      }
      for (int i = 1; i <= n; i++) {
            long long num = fre[ vec[i] ];
            long long myans = ans - num * (num - 1) / 2;
            num--;
            myans += num * (num - 1) / 2;
            cout << myans << endl;
      }
}

signed main() {
      ios_base::sync_with_stdio(false);
      cin.tie(nullptr); cout.tie(nullptr);

      if (fopen("in.txt", "r")) {
            freopen("in.txt", "r", stdin);
      }

      int tc = 1;
      while (tc--) {
            Task();
      }
}


Measured memory_bytes: 4696
#include <bits/stdc++.h>

using namespace std;

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

inline int toInt(string s) {int v; istringstream sin(s);sin>>v; return v;}

typedef long long ll;

int main(){
    int N;
    cin >> N;

    for(int i = 0; i <= N/4; i++){
        for(int j = 0; j <= N/7; j++){
            if(N == i*4 + j*7){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }

    cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 256
s = gets.chomp

i = 0
j = s.size - 1
ans = 0
bool = while i < j
    if s[i] == "x" && s[j] == "x"
        i += 1
        j -= 1
    elsif s[i] == "x"
        ans += 1
        i += 1
    elsif s[j] == "x"
        ans += 1
        j -= 1
    elsif s[i] == s[j]
        i += 1
        j -= 1
    else
        break true
    end
end

puts bool ? -1 : ans

Measured memory_bytes: 1916
if __name__ == '__main__':
    k, n = map(int, input().split())
    a = [int(i) for i in input().split()]
    max = 0
    max = a[0] + (k-a[n-1])
    bf = 0

    for i  in a:
        now = i -bf
        if now > max:
            max = now
        bf = i

    print(k-max)



Measured memory_bytes: 24908
#ifdef LOCAL111
	#define _GLIBCXX_DEBUG
#else
	#pragma GCC optimize ("O3")
	#define NDEBUG
#endif
// #define _USE_MATH_DEFINES
#include <bits/stdc++.h>
const int INF = 1e9;
using namespace std;
template<typename T, typename U> ostream& operator<< (ostream& os, const pair<T,U>& p) { os << '(' << p.first << ' ' << p.second << ')'; return os; }

#define endl '\n'
#define ALL(a)  (a).begin(),(a).end()
#define SZ(a) int((a).size())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#ifdef LOCAL111
	#define DEBUG(x) cout<<#x<<": "<<(x)<<endl
	template<typename T> void dpite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}
#else
	#define DEBUG(x) true
	template<typename T> void dpite(T a, T b){ return; }
#endif
#define F first
#define S second
#define SNP string::npos
#define WRC(hoge) cout << "Case #" << (hoge)+1 << ": "
template<typename T> void pite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
  for(auto &e:u) fill_v<T>(e,v...);
}

const array<int, 4> dx = {0, 1, 0, -1};
const array<int, 4> dy = {1, 0, -1, 0};


typedef long long int LL;
typedef unsigned long long ULL;
typedef pair<int,int> P;

void ios_init(){
	//cout.setf(ios::fixed);
	//cout.precision(12);
#ifdef LOCAL111
	return;
#endif
	ios::sync_with_stdio(false); cin.tie(0);
}

int main()
{
	ios_init();
	int n;
	while(cin >> n) {
		cout << n * n * n << endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;
 
//#define int long long
using ll = long long;
#define all(v) (v).begin(), (v).end()
#define rep(i,n) for(ll i=0;i<n;i++)
#define reps(i,n) for(ll i=0;i<=n;i++)

ll MOD = 1000000007;
const long long L_INF = 1LL << 60;
const int INF = 2147483647; // 2^31-1
const double PI = acos(-1);
 
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

int main(){
    ios_base::sync_with_stdio(false);
    ll k,flag=0;
    cin >> k;
    vector<ll> a(k,0);
    a[1]=7;
    for(int i=1;i<=k;i++){
        if(i!=1){
            a[i]=(10*a[i-1]+7);
            a[i]%=k;
        }
        if(a[i]%k==0){
            cout << i << endl;
            flag = 1;
            break;
        }
    }
    if(!flag){
    cout << -1 << endl;
    }
    return 0;
}


Measured memory_bytes: 11004
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fo(i,a,b) for(int i=a;i<b;i++)

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	long int n;
	cin>>n;
	long int a[n];
	for(long int i=0;i<n;i++)
	{
		a[i] = i+1;
	}
	long long int sum=0;
	for(long int i=0;i<n;i++)
	{
		long long int flag =0;
		if(a[i] % 3 == 0 || a[i]%5==0)
		{
			flag=0;
		}
		else
		{
			flag= a[i];
		}
		sum = flag + sum;
	}
	cout<<sum;
	//return 0;
}

Measured memory_bytes: 11460
#include <bits/stdc++.h>
using namespace std;

#define repeat(i, n) for (auto i = decltype(n)(); (i) < (n); (i)++)

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int n, k;
    cin >> n >> k;

    cout << 1 + (max(0, n - k) + k - 2) / (k - 1) << endl;

    return 0;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <queue>
#include <stack>
#include <list>
#include <functional>
#include <numeric>
#include <iostream>

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (n); ++i)

ll N, A[212345];

int main() {

	scanf("%lld", &N);
	rep(i, N) scanf("%lld", &A[i]);

	vector<ll> d;

	rep(i, N) d.push_back(A[i] - (i + 1));
	sort(d.begin(), d.end());

	ll a = 0;
	rep(i, N) {
		a += abs(A[i] - (d[N / 2] + i + 1));
	}

	printf("%lld\n", a);

	return 0;
}


Measured memory_bytes: 3956
#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    map<string,long long> count;
    string s[n];
    for (int i = 0; i < n; i++) {
        cin >> s[i];
        sort(s[i].begin(), s[i].end());
        count[s[i]]++;
    }

    long long ans = 0;
    for (const auto& x : count) {
        ans += x.second * (x.second - 1) / 2;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 18176
S=str(input())
n1=int(S[0:2])
n2=int(S[2:4])
 
YYMM = 0
MMYY = 0
 
if (n2 <= 12) and (n2 > 0):
    YYMM = 1
if (n1 <= 12) and (n1 > 0):
    MMYY = 1
if (MMYY == 1):
    if(YYMM == 1):
        print("AMBIGUOUS")
    else:
        print("MMYY")
elif (YYMM == 1):
    print("YYMM")
else:
    print("NA")

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int main(){
	string s;
	cin>>s;
	if(s=="SUN") cout<<7;
	else if(s=="SAT") cout<<1;
	else if(s=="MON") cout<<6;
	else if(s=="TUE") cout<<5;
	else if(s=="WED") cout<<4;
	else if(s=="THU") cout<<3;
	else if(s=="FRI") cout<<2;
	return 0;
}
	
	


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define eb emplace_back
#define pb push_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define elif else if
#define se second
#define fi first
typedef long long ll;
typedef multiset<ll> S;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef priority_queue<ll> PQ;
typedef priority_queue<ll,vector<ll>,greater<ll>> SPQ;
using vi=vector<ll>;
using vvi=vector<vector<ll>>;
const ll inf=1001001001001001;
const int INF=1001001001;
const ll mod=1000000007;
bool chmin(auto &a,auto b){if(a>b){a=b;return true;}return false;}
bool chmax(auto &a,auto b){if(a<b){a=b;return true;}return false;}

int main(){
    ll n;cin>>n;
    vi v(n);
    ll ans=0;
    rep(i,n)cin>>v[i];
    if(v[0]!=0){
        cout<<-1<<endl;
        return 0;
    }
    for(ll i=n-1;i>0;i--){
        ans+=v[i];
      	if(v[i]<0){
        	cout<<-1<<endl;
        	return 0;
      	}
        rep(j,v[i]-1){
            if(i-j-1<0){
                cout<<-1<<endl;
                return 0;
            }
            if(v[i-j-1]<=v[i]-j-1)v[i-j-1]-=v[i]-j-1;
          	else break;
          	if(v[i-j-1]<0){
            	cout<<-1<<endl;
            	return 0;
            }
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 1792
//Bismillahir Rahmanir Rahim
//In the name of Allah the Most Merciful
//Astagfirullahil laji Rabbi Minkulli Jamio
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define double long double
int i,j,k;
 main()
 {
     int a=0;
     int n;cin>>n;
     while(1)
     {
         if(a>=n) break;
         a+=1000;
     }
     cout<<a-n<<endl;
 }


Measured memory_bytes: 3632
#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
#define ll long long
using namespace std;

ll array[100005];


int main(){
	int N;
	ll K;
	cin >> N >> K;
	for(int i = 0; i < N; i++){
		int m,n;
		cin >> m >> n;
		array[m] += n;
	}

	for(int i = 1; i < 100005; i++){
		if(array[i]!=0) {
			if(K <= array[i]) {
				cout << i << endl;
				break;
			}

			else{
				K -= array[i];
			}
		}
	}

}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,k;
  cin>>n>>k;
  vector<int> v(n);
  for(int i=0; i<n; i++){
    cin>>v.at(i);
  }
sort(v.begin(),v.end());
int ans=0;
for(int i=0; i<k; i++){
  ans+=v.at(i);
}
cout<<ans<<endl;
return 0;
}


Measured memory_bytes: 3636
#include <iostream>
//#include <iomanip>
//#include <algorithm>
//#include <numeric>
//#include <queue>
//#include <stack>
//#include <math.h>
//#include <vector>
//#include <string>
//typedef long long LL;
using namespace std;

int main(){
    int a;
    int b;
    int ans;
    cin >> a >> b;
    if(a>=10 || b>=10){
        ans = -1;
    }else{
        ans = a*b;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=500010;
int pos[N],sz;
int cnt[N];
int a[N];
int ans[N];
ll res;
struct node
{
    int l,r,k;
    bool operator <(const node& o)const
    {
        if(pos[l]==pos[o.l]) return r<o.r;
        return pos[l]<pos[o.l];
    }
}q[N];
int n,m;
void add(int k)
{
    cnt[a[k]]++;
    if(cnt[a[k]]==1) res++;
}
void sub(int k)
{
    cnt[a[k]]--;
    if(cnt[a[k]]==0) res--;
}
int main()
{
    scanf("%d%d",&n,&m);
    sz=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        pos[i]=i/sz;
    }
    for(int i=0;i<m;i++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        q[i]={l,r,i};
    }
    sort(q,q+m);
    int l=1,r=0;
    for(int i=0;i<m;i++)
    {
        while(l<q[i].l) sub(l++);
        while(l>q[i].l) add(--l);
        while(r<q[i].r) add(++r);
        while(r>q[i].r) sub(r--);
        ans[q[i].k]=res;
    }
    for(int i=0;i<m;i++) printf("%lld\n",ans[i]);
    return 0;
}


Measured memory_bytes: 17404
#include <bits/stdc++.h>
 
//#include <unistd.h>
//#include <iostream>
 
using namespace std;
 
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl;
#define DEBUG_MAT(v) cerr<<#v<<endl;for(int i=0;i<v.size();i++){for(int j=0;j<v[i].size();j++) {cerr<<v[i][j]<<" ";}cerr<<endl;}
typedef long long ll;
//#define int ll
 
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
template<class S, class T> pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first + t.first, s.second + t.second); }
template<class S, class T> pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); }
template<class S, class T> ostream& operator<<(ostream& os, pair<S, T> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
#define X first
#define Y second
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(n);i>0;i--)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define in(x, a, b) (a <= x && x < b)
#define all(c) c.begin(),c.end()
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a = b; return 1; } return 0; }
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
const ll inf = 1000000001;
const ll INF = (ll)1e18 + 1;
const long double pi = 3.1415926535897932384626433832795028841971L;
#define Sp(p) cout<<setprecision(25)<< fixed<<p<<endl;
//int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
//int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
vi dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
vi dx2 = { 1,1,0,-1,-1,-1,0,1 }, dy2 = { 0,1,1,1,0,-1,-1,-1 };
#define fio() cin.tie(0); ios::sync_with_stdio(false);
//const ll MOD = 1000000007;
const ll MOD = 998244353;
// #define mp make_pair
//#define endl '\n'


signed main() {
    fio();
    string s;
    cin >> s;
    if (s == "AAA" or s == "BBB") {
        cout << "No" << endl;
    }   
    else {
        cout << "Yes" << endl;
    }
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int prime(int n)
{
	if(n < 2){
		return 0;
	} else if(n == 2){
		return 1;
	}
	
	if(n % 2 == 0){
		return 0;
	}
	
	for(int i = 3; i*i <= n; i+= 2){
		if(n % i == 0){
			return 0;
		}
	}
	
	return 1;
}

int main(int argc, char **argv)
{
	int n, c, i;
	int a[10] = {0, 9592, 17984, 25997, 33860, 41538, 49098, 56543, 63951, 71274};
	while(cin >> n){
		i = 0;
		c = 0;
		for(int j = 900000; j >= 100000; j -= 100000){
			if(j < n){
				i = j+1;
				c = a[j/100000];
				break;
			}
		}
		
		for(; i <= n; i++){
			if(prime(i) == 1){
				c++;
			}
		}
		
		cout << c << endl;
	}
	
	return 0;
}

Measured memory_bytes: 864
#include<iostream>
#include<algorithm>
using namespace std;
int n,a[2<<17],b[2<<17];
main()
{
	cin>>n;
	for(int i=0;i<n;b[i]=a[i],i++)cin>>a[i];
	sort(a,a+n);
	for(int i=0;i<n;i++)cout<<a[a[n/2]>b[i]?n/2:n/2-1]<<endl;
}


Measured memory_bytes: 3712
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=1;i<=(int)(n);i++)
using ll=long long;
const int MOD=998244353;
int main(){
    int n,m,ans=0;
    cin>>n>>m;
    vector<ll> w(n+1),v(n+1);
    rep(i,n) cin>>w[i]>>v[i];
    vector<vector<ll>> dp(n+10,vector<ll>(1e6,1e9+20));
    dp[0][0]=0;
    rep(i,n){
        for(int j=0;j<=1e5;j++){
            if(j-v[i]<0){
                dp[i][j]=dp[i-1][j];
                continue;
            }
            dp[i][j]=min(dp[i-1][j-v[i]]+w[i],dp[i-1][j]);
        }
    }
    ans=1e5;
    while(dp[n][ans]>m){
        ans--;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 870760
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <math.h>
#include <stdlib.h>
using namespace std;
int main(){
	int n,m;
	while(cin>>n>>m){
		if(n==0&&m==0) break;
		int h[n],w[m];
		for(int i=0;i<n;i++){
			cin>>h[i];
		}
		int y[n+1],nowy=0;
		y[0]=0;
		for(int i=0;i<n;i++){
			nowy=nowy+h[i];
			y[i+1]=nowy;
		}
		for(int i=0;i<m;i++){
			cin>>w[i];
		}
		int x[m+1],nowx=0;
		x[0]=0;
		for(int i=0;i<m;i++){
			nowx=nowx+w[i];
			x[i+1]=nowx;
		}
		int *hh=new int[1500001];
		int *ww=new int[1500001];
		for(int i=0;i<1500001;i++){
			hh[i]=0;
			ww[i]=0;
		}
		for(int i=0;i<n+1;i++){
			for(int j=i+1;j<n+1;j++){
				hh[y[j]-y[i]]++;
			}
		}
		for(int i=0;i<m+1;i++){
			for(int j=i+1;j<m+1;j++){
				ww[x[j]-x[i]]++;
			}
		}
		int k=0;
		for(int i=0;i<1500001;i++){
			k=k+ww[i]*hh[i];
		}
		cout<<k<<endl;
		delete[] hh;
		delete[] ww;
	}
    return 0;
}

Measured memory_bytes: 12876
#include <bits/stdc++.h>

using namespace std;
using ll =long long;
typedef pair<int,int> P;
#define SORT(a) sort((a).begin(),(a).end())
#define rSORT(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cerr << #x << " = " << (x) << endl;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//Write From this Line

int main()
{
	int n, m;
	cin >> n >> m;
	int h[n], ma[n];
	rep(i,n){
		cin >> h[i];
		ma[i] = 0;
	}
	rep(i,m){
		int a, b;
		cin >> a >> b;
		a--,b--;
		ma[a] = max(ma[a],h[b]);
		ma[b] = max(ma[b],h[a]);
	}
	int ans = 0;
	rep(i,n){
		ans += h[i] > ma[i];
	}
	cout << ans << endl;
}


Measured memory_bytes: 4364
#include<iostream>
#include<vector>
#include<queue>
#include<utility>
using namespace std;

#define rep(i,n) for(int i=0;i<(n);++i)

constexpr int dx[]={1,0,-1,0};
constexpr int dy[]={0,1,0,-1};
constexpr int ddx[] = {1,1,-1,-1,2,2,2,2,2,-2,-2,-2,-2,-2,1,0,-1,1,0,-1};
constexpr int ddy[] = {1,-1,1,-1,0,1,2,-1,-2,2,1,0,-1,-2,2,2,2,-2,-2,-2};
constexpr int INF = 1<<28;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  int H,W,C_h,C_w,D_h,D_w;
  cin>>H>>W>>C_h>>C_w>>D_h>>D_w;
  C_h--,C_w--,D_h--,D_w--;
  vector<string> S(H);
  rep(i,H)cin>>S[i];

  vector dist(H,vector(W,INF));
  vector seen(H,vector(W,false));
  dist[C_h][C_w] = 0;
  deque<pair<int,int>> deq;
  deq.emplace_front(C_h,C_w);
  while(!deq.empty()){
    auto [y,x] = deq.front();
    deq.pop_front();
    if(seen[y][x])continue;
    seen[y][x] = true;
    rep(i,4){
      int ny = y+dy[i];
      int nx = x+dx[i];
      if(ny>=0&&nx>=0&&ny<H&&nx<W&&S[ny][nx]=='.'){
        if(dist[ny][nx]>dist[y][x]){
          dist[ny][nx] = dist[y][x];
          deq.emplace_front(ny,nx);
        }
      }
    }
    rep(j,20){
      int ny = y+ddy[j];
      int nx = x+ddx[j];
      if(ny>=0&&nx>=0&&ny<H&&nx<W&&S[ny][nx]=='.'){
        if(dist[ny][nx]>dist[y][x]+1){
          dist[ny][nx] = dist[y][x]+1;
          deq.emplace_back(ny,nx);
        }
      }
    }
  }
  int ans = dist[D_h][D_w];
  cout<<(ans==INF?-1:ans)<<endl;
}


Measured memory_bytes: 8916
#include "bits/stdc++.h"
using namespace std;
#define REP(i, n) for(ll i = 0;i < n;i++)
#define ll long long
#define MOD 1000000007LL
#define llMAX 9223372036854775807LL
#define llMIN -9223372036854775808LL
using vi = vector<ll>; // intの1次元の型に vi という別名をつける
using vvi = vector<vi>; // intの2次元の型に vvi という別名をつける
 
ll n,k,x,y,a;
 
int main(){
  ll ans=0;
  double b;
  cin >> a >> b;
 
  ll lb=(b*100.0+0.5);
  
  ans=a*lb/100;
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 3716
#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
  return *(long int *)a - *(long int *)b;
}

int main() {
  long int N, x, a[100];

  long int i;

  scanf("%ld %ld", &N, &x);

  for (i = 0; i < N; i++) {
    scanf("%ld", &a[i]);
  }

  qsort(a, N, sizeof(long int), compare);

  for (i = 0; i < N && x > 0; i++) {
    x -= a[i];
  }

  if (x != 0) {
    i--;
  }

  printf("%ld\n", i);

  return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>

#ifdef _PRINTDEBUG
  #include "lib/printdebug.hpp"
#else
  #define printdebug(...) 1
#endif
#define MOD_1_000_000_007 (1000000007LL)
#define LINF (1LL<<60)
#define rep(i, n)   for (long long i = 0; i <  (long long)(n); i++)
#define rep1(i, n)  for (long long i = 1; i <  (long long)(n); i++)
#define rep2(i, n)  for (long long i = 2; i <  (long long)(n); i++)
#define rep0c(i, n) for (long long i = 0; i <= (long long)(n); i++)
#define rep1c(i, n) for (long long i = 1; i <= (long long)(n); i++)
#define rep2c(i, n) for (long long i = 2; i <= (long long)(n); i++)
#define repc0(n, i) for (long long i = (long long)(n); i >= 0; i--)
#define repc1(n, i) for (long long i = (long long)(n); i >= 1; i--)
#define repc2(n, i) for (long long i = (long long)(n); i >= 2; i--)
#define REP(i, n, m) for (long long i = (long long)(n); i < (long long)(m); i++)

namespace solver {
  using namespace std;
  typedef long long ll;

  ll N, M;

  void init() {
    scanf("%lld %lld", &N, &M);
  }

  void solve() {
    if(N%2) {
      ll r = N;
      rep1c(i, M) {
        cout << i << " " << r-i+1 << endl;
      }
    } else {
      ll r = N;
      ll mid = M/2;
      if(M%2) mid++;
      for(ll i = 1; i <= mid; i++) {
        cout << i << " " << r-i+1 << endl;
      }
      for(ll i = mid+1; i <= M; i++) {
        cout << i+1 << " " << r-i+1 << endl;
      }
    }
  }
}

int main() {
  solver::init();
  solver::solve();
  return 0;
}

Measured memory_bytes: 3776
#include<iostream>
using namespace std;

int main()
{
  int N,ind=1;
  string h,A[50],B[50],C[50],D[50];

  cin >> N;
  

  for(int i=1;i<=N;i++)
    {
      cin >> A[i];

      B[i] = A[i];

      C[i] = A[i];
    }

  //遅いが安定しているsortを作成する
  for(int i=1;i<=36;i++)
    {
      for(int j=1;j<=N;j++)
	{
	  if(C[j][1]-'0' == i)
	    {
	      D[ind].clear();
	      D[ind].insert(0,C[j]);
	      ind++;
	    } 
	}
    }
  



  for(int i=1;i<=N;i++)
    {
      for(int j=N;j>=i+1;j--)
	{
	  
	  if(A[j][1]-'0' < A[j-1][1]-'0')
	    {
	      h.clear();
	      h.insert(0,A[j]);
	      A[j].clear();
	      A[j].insert(0,A[j-1]);
	      A[j-1].clear();
	      A[j-1].insert(0,h);
	    }
	}
    }


  //安定しているsortで作成された基準の配列Dと比較し、異なる部分があれば Not stableとする
  bool stable=true;
  for(int i=1;i<=N;i++)
    {
      if(A[i] != D[i])
	{
	  stable=false;
	  break;
	}
    }

  for(int i=1;i<=N;i++)
    {
      cout << A[i];
      if(i != N)cout << " ";
    }
  cout << endl;
  if(stable)cout << "Stable" << endl;
  else cout << "Not stable" << endl;


  for(int i=1;i<=N;i++)
    {
      int mini=i;
      for(int j=i;j<=N;j++)
	{
	  if(B[j][1]-'0'<B[mini][1]-'0')
	    {
	      mini = j;
	    }
	}
      h.clear();
      h.insert(0,B[i]);
      B[i].clear();
      B[i].insert(0,B[mini]);
      B[mini].clear();
      B[mini].insert(0,h);
    }
 
  stable = true;
 for(int i=1;i<=N;i++)
    {
      if(B[i] != D[i])
	{
	  stable=false;
	  break;
	}
    }

  for(int i=1;i<=N;i++)
    {
      cout << B[i];
      if(i != N)cout << " ";
    }
  cout << endl;
  if(stable)cout << "Stable" << endl;
  else cout << "Not stable" << endl;

  return 0;
}

Measured memory_bytes: 0