akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility>
#include <unordered_map>
#include <cmath>
using namespace std;

typedef unsigned int uint;
typedef long long llong;
typedef unsigned long long ullong;
// -2.1e-9 <= int <= 2.1e9
// -9.2e-18 <= long long <= 9.2e18
// 0 <= unsigned int <= 4.2e9
// 0 <= unsigned long long <= 18.4e18

int main()
{
    int A, B, C, D;
    cin >> A >> B >> C >> D;
    int cnt = 0;
    while(true) {
        if (cnt % 2 == 0) {
            C = C - B;
            if (C <= 0) {
                cout << "Yes" << endl;
                return 0;
            }
        }
        else {
            A = A - D;
            if (A <= 0) {
                cout << "No" << endl;
                return 0;
            }
        }
        cnt++;
    }
}


Measured memory_bytes: 3632
#include <iostream>
#include <string>
#include <vector>

using namespace std;

unsigned short dp[7][1000000];
unsigned char pr[7][1000000];
int df[7][1000000];

int main(){
	while(true){
		int n;
		string s;
		cin >> n >> s;
		if(n == 0 && s == "0"){ break; }
		const int m = s.size();
		for(int i = 0; i <= m; ++i){
			for(int j = 0; j <= n; ++j){
				dp[i][j] = pr[i][j] = df[i][j] = 0;
			}
		}
		dp[0][0] = 1;
		for(int i = 0; i < m; ++i){
			int x = 0;
			for(int j = i; j < m; ++j){
				x = (x * 10) + s[j] - '0';
				if(x > n){ break; }
				for(int k = 0; k + x <= n; ++k){
					if(dp[i][k] == 0){ continue; }
					dp[j + 1][k + x] += dp[i][k];
					pr[j + 1][k + x] = i;
					df[j + 1][k + x] = x;
				}
			}
		}
		int answer = -1;
		for(int i = n; answer < 0 && i >= 0; --i){
			if(dp[m][i] != 0){ answer = i; }
		}
		if(answer < 0){
			cout << "error" << endl;
		}else if(dp[m][answer] >= 2){
			cout << "rejected" << endl;
		}else{
			cout << answer;
			vector<int> cut;
			int r = m, c = answer;
			do {
				const int d = df[r][c];
				cut.push_back(d);
				r = pr[r][c];
				c -= d;
			} while(r > 0);
			for(int i = cut.size() - 1; i >= 0; --i){
				cout << " " << cut[i];
			}
			cout << endl;
		}
	}
	return 0;
}

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

int main() {
    int A[3][3] = {0};
    int N;
    for (int i=0; i<3; i++) {
        cin >> A[i][0] >> A[i][1] >> A[i][2];
    }
    cin >> N;
    int b[N];
    for (int i=0; i<N; i++) {
        cin >> b[i];
    }
    
    int B[3][3] = {0};
    bool res = false;
    //数字の場所をチェック
    for (int i=0; i<3; i++) {
        for (int j=0; j<3; j++) {
            for (int k=0; k<N; k++) {
                if (A[i][j] == b[k]) {
                    B[i][j] = b[k];
                }
            }
        } 
    }
    // 横チェック
    for (int i=0; i<3; i++) {
        if (B[0][i] * B[1][i] * B[2][i] != 0) {
            res = true;
        }
    }
    // 縦チェック
    for (int i=0; i<3; i++) {
        if (B[i][0] * B[i][1] * B[i][2] != 0) {
            res = true;
        }
    }
    //斜めチェック
    if (B[0][0] * B[1][1] * B[2][2] != 0) {
        res = true;
    }
    if (B[0][2] * B[1][1] * B[2][0] != 0) {
        res = true;
    }

    if (res == true) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include <stdio.h>

int check(int,int,int*);

int main(){
  int H,W;
  int answer;
  scanf("%d%*c%d\n",&H,&W);
  char a;
  int array[26];
  for(int i=0;i<26;i++){
    array[i] = 0;
  }
  int k;
  for(int i=0;i<H;i++){
    for(int j=0;j<W-1;j++){
      scanf("%c",&a);
      k = a - 'a';
      array[k] += 1;
    }
    scanf("%c\n",&a);
    k = a - 'a';
    array[k] += 1;
  }
  int amari[4];
  for(int i=0;i<4;i++){
    amari[i]=0;
  }
  for(int i=0;i<26;i++){
    amari[0] += array[i]/4;
    k = array[i]%4;
    if(k != 0){
      amari[k]++;
    }
  }
  if(amari[1]+amari[3] > 1){
    answer = 0;
  }else{
    answer = check(H,W,amari);
  }
  if(answer == 1){
    printf("Yes");
  }else{
    printf("No");
  }
  return 0;
}
 
int check(int H,int W,int *amari){
  if(H>1 && W>1){
    if(amari[0] >= (H/2)*(W/2)){
      amari[0] -= (H/2)*(W/2);
      if(H%2 == 0 && W%2 == 0){
	return 1;
      }
    }else{
      return 0;
    }
  }
  amari[2] += amari[3] + amari[0]*2;
  if(H%2 == 1){
    amari[2] -= W/2;
  }
  if(W%2 == 1){
    amari[2] -= H/2;
  }
  if(amari[2] == 0){
    return 1;
  }else{
    return 0;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define N 20000
typedef long long ll;
#define ALL(v) (v).begin(),(v).end()
#define SZ(x) int(x.size())
#define OUT(a) cout<<(a)<<endl
typedef pair<int,int> P;
#define INF 1000000000
const int MAX = 1000000;
const int MOD = 1000000007;

int main(){
	int n;
    string s;
    cin>>n>>s;
    REP(i,SZ(s)){
        s[i]='A'+(s[i]-'A'+n)%26;
    }
    OUT(s);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
const ll mod = ll(1e9) + 7;
const int INF = int(1e9);

int main()
{
    int N, M;
    cin >> N >> M;
    vector<pair<ll, ll>> AB(N);
    rep(i, N) cin >> AB[i].first >> AB[i].second;
    sort(AB.begin(), AB.end());
    ll ans = 0;
    rep(i, N)
    {
        if (AB[i].second <= M)
        {
            ans += AB[i].first * AB[i].second;
            M -= AB[i].second;
        }
        else
        {
            ans += AB[i].first * M;
            M = 0;
        }
        if (M == 0)
        {
            cout << ans << endl;
            return 0;
        }
    }

    return 0;
}


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

int main() {
  string s;
  cin>>s;
  if (s[0] != 'A') {
     cout<<"WA"<<endl;
     return 0;
  }
  int cnt = 0;
  for (int i=2; i<s.length()-1; i++) {
    if (s[i] == 'C') {
      ++cnt;
    }
  }
  if (cnt != 1) {
     cout<<"WA"<<endl;
     return 0;
  }
  for (int i=0; i<s.length(); i++) {
    if (s[i] == 'A' || s[i] == 'C') {
      continue;
    }
    if (s[i] >= 'a' && s[i] <= 'z') {
      continue;
    }
    cout<<"WA"<<endl;
    return 0;
  }
  cout<<"AC"<<endl;
}

Measured memory_bytes: 764
def solve(string):
    n, m, *ab = map(int, string.split())
    ans = 0
    for a, b in sorted([(a, b) for a, b in zip(ab[::2], ab[1::2])]):
        ans += a * min(b, m)
        m -= b
        if m <= 0:
            break
    return str(ans)


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(n)])))


Measured memory_bytes: 26748
#include <bits/stdc++.h>
#include<math.h>
#define ll long long
#define fi first
#define se second
#define ld long double
#define mod 1000000007
using namespace std;
int main()
{
     ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
ll n,k,i,j;
cin>>n>>k;
vector<ll>v(n),v1(n,LONG_LONG_MAX);
for(i=0;i<n;i++)
    cin>>v[i];
v1[0]=0;
for(i=0;i<n;i++)
{
    for(j=i+1;j<n && j-i<=k;j++)
    {
        v1[j]=min(v1[j],(ll)(v1[i]+fabs(v[i]-v[j])));
    }
}
cout<<v1[n-1];
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int dp[N][N],n,m;
char ch[N][N];
int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};
struct node{
	int x,y;
};
node st,ed;
deque<node>q;
inline void bfs(){
	memset(dp,0x3f,sizeof dp);
	dp[st.x][st.y]=0;
    q.push_front({st.x,st.y});
    while(q.size()){
    	auto t=q.front();q.pop_front();
    	int d=dp[t.x][t.y];
    	//printf("%d %d %d\n",t.x,t.y,d);
    	for(int i=0;i<4;i++){
    		int x=t.x+dx[i],y=t.y+dy[i];
    		//printf("%d %d\n",x,y);
    		if(x<1||x>n||y<1||y>m||ch[x][y]=='#'||dp[x][y]<=d)continue;
    		//print("") 
    		dp[x][y]=d;
    		q.push_front({x,y});
		}
		for(int i=t.x-2;i<=t.x+2;i++)
		for(int j=t.y-2;j<=t.y+2;j++){
			if(i<1||i>n||j<1||j>m||ch[i][j]=='#'||dp[i][j]<=d+1)continue;
			dp[i][j]=d+1;
			q.push_back({i,j});
		}
	}
}
int main(){
	
	scanf("%d%d",&n,&m);
	scanf("%d%d",&st.x,&st.y);
	scanf("%d%d",&ed.x,&ed.y);
	for(int i=1;i<=n;i++){
		scanf("%s",ch[i]+1);
	}
	bfs();
	if(dp[ed.x][ed.y]==0x3f3f3f3f)printf("-1\n");
	else printf("%d\n",dp[ed.x][ed.y]);
	return 0;
}


Measured memory_bytes: 8680
import sys

sys.setrecursionlimit(200000)


def input():
    return sys.stdin.readline()[:-1]


def ii(t: type = int):
    return t(input())


def il(t: type = int):
    return list(map(t, input().split()))


def imi(N: int, t: type = int):
    return [ii(t) for _ in range(N)]


def iml(N: int, t: type = int):
    return [il(t) for _ in range(N)]


def solve():
    N = ii()
    A = [0]+imi(N)
    current = 1
    for i in range(1, 100001):
        current = A[current]
        if current == 2:
            return i
    return -1


if __name__ == "__main__":
    print(solve())


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

int main() {
    ll n;
    cin >> n;
    vector<ll> a(n+1);
    vector<ll> b(n);
    rep(i,n+1) cin >> a[i];
    rep(i,n) cin >> b[i];
    ll ans = 0, t = 0;
    rep(i,n) {
        ll m = min(a[i]-t, b[i]);
        ans += m+t;
        t = min(a[i+1], b[i]-m);
    }
    ans += min(a[n], t);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4816
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n,w = map(int,ipt().split())
    tng = [tuple(map(int,ipt().split())) for i in range(n)]
    dp = [[0]*(3*n) for i in range(n+1)]
    w1 = tng[0][0]
    ma = 0
    for ni,(wi,vi) in enumerate(tng):
        dw = wi-w1
        for i in range(ni+1,0,-1):
            for j in range(dw,3*n):
                if dp[i-1][j-dw]+vi > dp[i][j]:
                    dp[i][j] = dp[i-1][j-dw]+vi

    ans = 0
    for i in range(n+1):
        rw = w-i*w1
        if rw < 0:
            break
        ti = max(min(3*n-1,rw),0)
        if ans < dp[i][ti]:
            ans = dp[i][ti]

#    print(dp)
    print(ans)
    return None

if __name__ == '__main__':
    main()


Measured memory_bytes: 70628
#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;
#define lli long long int
#define llu unsigned long long int
#define pb push_back
#define rt return 0
#define endln "\n"
#define all(x) x.begin(), x.end()
#define sz(x) (lli)(x.size())
const lli MOD = 1e9 + 7;
const double PI = 2 * acos(0.0);
// cout << fixed << setprecision(0) << pi <<endl;
// typedef tree<int, null_type, less<int>, rb_tree_tag,
//              tree_order_statistics_node_update>
//     new_data_set;
// for multiset
// typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
//              tree_order_statistics_node_update>
//     new_data_set;
// order_of_key(val): returns the number of values less than val
// find_by_order(k): returns an iterator to the kth largest element (0-based)

void solve() {
    lli n, a;
    string s, t;
    cin >> s >> t;

    lli ans = s.length() + 5;
    for (lli i = 0; i <= s.length() - t.length(); i++) {
        lli cnt = 0;
        for (lli j = 0; j < t.length(); j++) {
            if (t[j] != s[j + i]) {
                cnt++;
            }
        }
        ans = min(ans, cnt);
    }

    cout << ans << endl;
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // lli t; cin >> t; while(t--)
    solve();
    rt;
}

Measured memory_bytes: 3660
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;

int main(){
    int n;
    cin>>n;
    vector<int> c(n-1),s(n-1),f(n-1);
    for(int i=0;i<n-1;i++){
        cin>>c[i]>>s[i]>>f[i];
    }
    vector<int> ans(n);
    for(int i=0;i<n-1;i++){
        int res=0;
        for(int j=i;j<n-1;j++){
            if(j==i){
                res+=s[j];
                res+=c[j];
                continue;
            }
            if(res<=s[j]){
                res=s[j]+c[j];
                continue;
            }            
            int num;
            if(0==(res-s[j])%f[j]){
                num=(res-s[j])/f[j];
            }else{
                num=(res-s[j])/f[j]+1;
            }
            res=s[j]+num*f[j]+c[j];
        }
        ans[i]=res;
    }
    for(int i=0;i<n;i++){
        cout<<ans[i]<<endl;
    }
    return 0;
}

Measured memory_bytes: 3648
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MOD = 1e9+7;
using ll = long long;
using vi = vector<int>;
#define rep(i, n) for (int i = 0; i < n; i++)
#define ALL(x) x.begin(), x.end()

using namespace std;
int main(){
  vi ans(1000001,0);
  for(int i=1;i<1000000;i++){
   for(int j=1;j<1000000;j++){
     if(i*j>1000000) break;
     ans.at(i*j)++;
   }
  }
  ll a,tmp=0;
  cin >> a;
  rep(i,a){
    tmp += ans.at(i);
  }
  cout << tmp;
}


Measured memory_bytes: 7032
//abc102_c.cpp
//Sat Jul  7 20:09:56 2018

#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
using ll=long long;

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

	int a[n];
	a[0] = 0;
	for (int i=0;i<n;i++){
		cin >> a[i];
		a[i] = a[i] - i - 1;
	}

	sort (a,a+n);

	int med = 0;

	if (n%2==1){
		int temp = floor(n/2);
		med = a[temp];
	}else {
		med = (a[n/2]+a[n/2-1])/2;
	}

	ll ans = 0;

	for (int i=0;i<n;i++){
		ans += abs (a[i]-med);
	}

	cout << ans << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int N, K, C;
string S;

int A[200005], B[200005], P[200005], sum[200005];

int main(void) {

	cin >> N >> K >> C;
	cin >> S;

	S = "$" + S + "$";

	for (int i = 1; i <= N; i++) {
		if (S[i] == 'o') {
			if (i - C - 1 >= 1) {
				A[i] = A[i - C - 1] + 1;
			}
			else { A[i] = 1; }
		}
		else { A[i] = A[i - 1]; }
	}

	

	for (int i = N; i >= 1; i--) {
		if (S[i] == 'o') {
			if (i + C + 1 <= N) { B[i] = B[i + C + 1] + 1; }
			else { B[i] = 1; }
		}
		else {
			B[i] = B[i + 1];
		}
	}


	if (C > 0) {
		/*for (int i = 1; i + C + 1 <= N; i++) {
			if (A[i] + B[i + C + 1] >= K) {
				for (int j = i + 1; j <= i + C; j++) { P[j] = 1; }
			}
		}*/

		for (int i = 1; i <= C; i++) {
			if (B[i + 1] >= K) { P[i] = 1; }
		}

		for (int i = N - C + 1; i <= N; i++) {
			if (A[i - 1] >= K) { P[i] = 1; }
		}



		for (int i = 1; i + C + 1 <= N; i++) {
			if (A[i] + B[i + C + 1] >= K) { sum[i + 1]++; sum[i + C + 1]--; }
		}


		for (int i = 1; i <= N; i++) {
			sum[i] += sum[i - 1];
		}

		for (int i = 1; i <= N; i++) {
			P[i] += sum[i];
		}

	}
	else {
		for (int i = 1; i <= N; i++) {
			if (A[i - 1] + B[i+1] >= K) { P[i] = 1; }
		}
	}

/*	for (int i = 1; i <= N; i++) {
	cout << "A[" << i << "]= " << A[i] <<" B["<<i<<"]= "<<B[i]<< " P["<<i<<"]= "<< P[i] <<" sum["<<i<<"]= "<<sum[i]<< endl;
	}*/


	for (int i = 1; i <= N; i++) {
		if (S[i] == 'o' && P[i] <= 0) { cout << i << endl; }
	}
	
	return 0;
}

Measured memory_bytes: 3776
days = input()
consecutive_days = 0
max_days = 0

if 'R' in days:
    max_days = 1
    consecutive_days = 1

for weather in range(len(days) - 1):
    if days[weather] == days[weather + 1] and days[weather] == 'R':
        consecutive_days += 1
        if consecutive_days > max_days:
            max_days = consecutive_days

print(max_days)

Measured memory_bytes: 9028
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb                 push_back
#define bug(x)             cerr<<#x<<" "<<x<<endl;
#define T int time;        scanf("%d", &time); while(time--)
    vector<ll>ar;
  bool check(ll i,ll n){
    if(abs(i-n)<=1)return true;
    for(ll ii=n-1; ii>i; ii--)if(ar[ii]<ar[ii-1])
      cout<<ar[ii]<<" ";
    cout<<endl;
    return true;
  }

   int main(){
      vector<ll>ad;
      ll n;
      cin>>n;
      ll ar[n+5];
      for(ll i=0; i<n; i++)cin>>ar[i];
      ad.pb(ar[0]);
    ll ans=0;
    ll mn=2222222;
    for(ll i=0; i<n; i++){ 
          if(mn>ar[i])ans++;
           mn=min(mn,ar[i]);
    }
     cout<<ans<<endl;
   

     }
   

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

using namespace std;

int main(){
    int N,K,X,Y;
    cin>>N>>K>>X>>Y;
    int sum,sum1,sum2,day2;
    sum1 = K*X;
    day2 = N - K;

    if(day2 <= 0){
        sum = N * X;
        cout << sum << endl;

        return 0;
    }

    sum2 = day2 * Y;

    sum = sum1 + sum2;

    cout << sum << endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		while(sc.hasNextInt()){
			ArrayList<Integer> list = new ArrayList<Integer>();
		int n = sc.nextInt();
		int m = sc.nextInt();
		if(n == 0 && m == 0)break;
		for(int i = 1; i <= n; i++)
			list.add(i);
		
		int x = -1;
		while(list.size() > 1){
			x = (x + m) % list.size();
			list.remove(x);
			x = x - 1;
		}
		System.out.println(list.get(0));	
		}
		}
}

Measured memory_bytes: 17336
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    int x, y;
    cin >> x >> y;
    cout << x + y / 2;
}


Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
//#include <bits/stdc++.h>
#include<vector>
#include<float.h>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
#include<math.h>
#include<cmath>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include <cassert>
#include <cmath>
#include<cstdint>

#define INF 1e9
#define rep(i,n)for(int i=0;(i)<(int)(n);i++)
#define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define vec(type,n) vector<type>(n)
#define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))
#define ALL(a)  (a).begin(),(a).end()

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<ll, ll>;

bool seen[300000];
Graph G(300000);
bool f;
int g;
void dfs(int v, int cnt){
    seen[v] = true;
    if(v == g){
        f = true;
        return;
    }
    if(cnt == 2)return;
    for(int nv : G[v]){
        if(seen[nv])continue;
        dfs(nv, cnt+1);
    }

}

int main(){
    int n, m;
    cin >> n >> m;
    rep(i, m){
        int a, b;
        cin >> a >> b;
        a--;b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    g = n -1;
    dfs(0, 0);
    cout << (f ? "POSSIBLE" : "IMPOSSIBLE");
    
}



Measured memory_bytes: 14448
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int a[15],b[15],f[15][1000005];
int main(void)
{
	memset(f,0x3F,sizeof(f));f[0][0]=0;
	int i,j,k,n,m,ans=0x3F3F3F3F;
	scanf("%d%d",&n,&m);m/=100;
	for(i=1;i<=n;++i)scanf("%d%d",&a[i],&b[i]),b[i]/=100;
	for(i=1;i<=n;++i)
	{
		for(j=a[i]-1;j>=0;--j)
		{
			for(k=1000000;k>=i*j;--k)f[i][k]=min(f[i][k],f[i-1][k-i*j]+j);
		}
		for(j=1000000;j>=i*a[i]+b[i];--j)f[i][j]=min(f[i][j],f[i-1][j-i*a[i]-b[i]]+a[i]);
	}
	for(j=m;j<=1000000;++j)ans=min(ans,f[n][j]);
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 58880
#include <stdio.h>

long f(long x)
{
    return x * x;
}

long calculate_area(long d)
{
    long i, sum = 0;

    for (i = 1; i < 600 / d; i++)
        sum += d * f(i * d);

    return sum;
}

int main(void)
{
    long d;

    while (scanf("%ld", &d) != EOF)
        printf("%ld\n", calculate_area(d));

    return 0;
}

Measured memory_bytes: 596
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int sz=1e5+9;
int n,k;
pair<long long,long long> p[sz];
long long ans;
bool f[sz];
long long cnt,tmp;
long long have;
stack<long long> q;

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    scanf("%d %d",&n,&k);
    for(int i=0;i<n;i++) scanf("%lld %lld",&p[i].y,&p[i].x);
    sort(p,p+n,greater<pair<long long,long long>>());
    for(int i=0;i<n;i++){
        if(have<k){
            tmp+=p[i].x;
            if(!f[p[i].y]){
                cnt++;
                f[p[i].y]=1;
            }else q.push(p[i].x);
            have++;
            ans=max(ans,tmp+cnt*cnt);
        }else if(have==k){
            if(f[p[i].y]) continue;
            if(q.empty()) break;
            long long curr=q.top();
            q.pop();
            tmp-=curr;
            tmp+=p[i].x;
            cnt++;
            f[p[i].y]=1;
            ans=max(ans,tmp+cnt*cnt);
        }
    }
    printf("%lld",ans);
    return 0;
}


Measured memory_bytes: 2176
#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;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

const ll INF = ll(1e15);

ll mult(ll a, ll b)
{
	if(a > INF/b) return INF;
	else return a*b;
}

ll power(ll a, ll b)
{
	ll r = 1;
	while(b)
	{
		if(b&1)
		{
			r = mult(r,a);
		}
		a = mult(a,a);
		b>>=1;
	}
	return r;
}

ll a;
ll solve(ll t)
{
	ll ans = t;
	for(ll i = 1; (a*i < t && i <= 50); i++)
	{
		ll remtime = t - a*i;
		if(remtime <= i) continue;
		ll mod = remtime%(i+1);
		ll up = (remtime)/(i+1);
		ans = max(ans, mult(power(up+1,mod),power(up,i+1-mod)));
	}
	return ans;
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	ll n;
	cin>>n>>a;
	ll lo = 1; ll hi = n;
	ll ans = 0;
	while(lo<=hi)
	{
		ll mid = (lo+hi)>>1;
		if(solve(mid)>=n)
		{
			ans=mid;
			hi=mid-1;
		}
		else
		{
			lo=mid+1;
		}
	}
	cout<<ans<<'\n';
}


Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4,sse4.1,sse4.2,avx,tune=native")
#include <bits/stdc++.h>

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int MD = (int)1e9 + 7; typedef vector<ll> VL;
void dbg(){ cerr << "\n"; }  template <class T, class ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }
template <class T> void amax(T& a,T b){if(a < b) a = b;}


int main(){
	cin.tie(0); ios_base::sync_with_stdio(false);
	int x, y, z, k;
	cin >>x >>y >>z >>k;
	VL a(x), b(y), c(z);
	rep(i, x) cin >>a[i];
	rep(i, y) cin >>b[i];
	rep(i, z) cin >>c[i];
	
	VL ab; ab.reserve(x*y);
	rep(i, x) rep(j, y) ab.push_back(a[i]+b[j]);
	sort(ab.rbegin(), ab.rend());
	if(sz(ab) > k) ab.resize(k);
	sort(c.rbegin(), c.rend());
	VL abc; abc.reserve(z*sz(ab));
	rep(i, sz(ab)) rep(j, z){
		if(i + j > k+3) break;
		abc.push_back(ab[i]+c[j]);
	}
	sort(abc.rbegin(), abc.rend());
	
	rep(i, k) cout << abc[i] <<"\n";
	return 0;
}


Measured memory_bytes: 29440
n = int(input())
a = list(map(int, input().split()))

count = 0
first = 0

while first < n:
    for i in range( n-1, first, -1 ):
        if a[i] < a[i-1]:
            t = a[i]
            a[i] = a[i-1]
            a[i-1] = t
            count += 1
    first += 1

print(*a)
print(count)

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

double n,k;

int suc_calc(int a,int b){
    if(a>=k) return 0;
    return suc_calc(a*2,b) +1;
}

int main(){
    cin>>n>>k;
    double ans=0.0;

    for(double i=1;i<=n;i++){
        if(i<k){
            ans+= 1/n * pow(0.5,suc_calc(i,k));
        }
        else{
            ans+=1.0/n;
        }
    }
    printf("%.13f\n", ans);
}

Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections.Generic;
class P
{
    static void Main()
    {
        int[] a = Console.ReadLine().Split().Select(int.Parse).ToArray();
        //白、A個の連結成分
        //黒、B個の連結成分

        //クソデカ#塊50*100の中に.をインプリメント
        //クソデカ.塊50*100の中に#をインプリメント
        char[][] res = Enumerable.Range(0, 100).Select(x => Enumerable.Repeat((x < 50 ? '#' : '.'), 100).ToArray()).ToArray();
        a[0]--;
        for (int i = 0; i < 25; i++)
        {
            for (int j = 0; j < 50; j++)
            {
                if (a[0] == 0) goto end1;
                res[i * 2][j * 2] = '.';
                a[0]--;
            }
        }
        end1:;
        a[1]--;
        for (int i = 0; i < 25; i++)
        {
            for (int j = 0; j < 50; j++)
            {
                if (a[1] == 0) goto end2;
                res[51 + i * 2][j * 2] = '#';
                a[1]--;
            }
        }
        end2:;

        Console.WriteLine("100 100");
        Console.WriteLine(string.Join("\n",res.Select(x => string.Join("",x)).ToArray()).ToArray());
    }
}


Measured memory_bytes: 13536
#include<stdio.h>
#define N_MAX 1400
#define min(a,b) ((a)<(b) ? (a):(b))
#define max(a,b) ((a)>(b) ? (a):(b))
int A[N_MAX][N_MAX],B[N_MAX][N_MAX];
int main(void){
    int h,w;
    int i,j,k;
    int ans=0;

    scanf("%d%d",&h,&w);
    for(i=0;i<h;i++){
	for(j=0;j<w;j++){
	     scanf("%d",&A[i][j]);
	     if(A[i][j]==1) B[i][j]=0;
	     else {
		B[i][j]=1;
		ans=1;
	     }
	}
    }

/*
    for(i=0;i<h;i++){
	for(j=0;j<w;j++){
	    if(j) printf(" ");
	    printf("%d",B[i][j]);
	}
	printf("\n");
    }
*/

    for(i=1;i<h;i++){
	for(j=1;j<w;j++){
	    if(B[i][j]!=0)
		B[i][j]=min(min(B[i-1][j],B[i-1][j-1]),B[i][j-1])+1;
	    ans=max(ans,B[i][j]);
	}
    }

    printf("%d\n",ans*ans);

    return 0;
}

Measured memory_bytes: 15912
#include <bits/stdc++.h>
#define ss second
#define ff first
#define all(x) x.begin(), x.end()
 
using namespace std;
using ll = long long;
using pii = pair<int, int>;
 
const int oo = 1e9 + 7;
const int mod = 1e9 + 7, maxn = 100100;
const long double PI = acos(-1);
 
int main (){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m, s, c, zero = '0';
    cin >> n >> m;
    bool impossible = false;
    string ans(n, '.');

    for (int i=0; i<m; i++){
        cin >> s >> c;
        if (ans[s-1] != '.' and ans[s-1] - '0' != c ){
            impossible = true;
        }
        else {
            ans[s-1] = char('0' + c);
        }
    }

    if (impossible) cout << -1 << endl;
    else{
        for (int i=0; i<ans.size(); i++){
            if (ans[i] == '.') {
                if (i == 0 and n != 1) ans[i] = '1';
                else ans[i] = '0';
            }
        }
        if (ans[0] != '0' || n == 1) cout << ans << endl;
        else cout << -1 << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define all(x) (x).begin(),(x).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 (b<a) { a=b; return 1; } return 0; }

typedef long long ll;

using namespace std;
string acgt="ACGT";
bool ok(int z,int a,int b,int c)
{
  if(a==0&&b==2&&c==1)return 0;
  if(a==0&&b==1&&c==2)return 0;
  if(a==2&&b==0&&c==1)return 0;
  if(z==0&&a==2&&c==1)return 0;
  if(z==0&&b==2&&c==1)return 0;
  return 1;
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  int mod=1e9+7;
  cin>>n;
  int dp[101][4][4][4];
  rep(i,4)rep(j,4)rep(l,4)rep(k,101)dp[k][i][j][l]=0;
  rep(i,4)rep(j,4)rep(l,4)if(ok(-1,i,j,l))dp[3][i][j][l]=1;
  repi(i,3,n)
  {
    rep(j,4)rep(k,4)rep(l,4)
    {
      rep(m,4)
      {
        if(ok(j,k,l,m))dp[i+1][k][l][m]+=dp[i][j][k][l];
        dp[i+1][k][l][m]%=mod;
      }
    }
  }
  int res=0;
  rep(i,4)rep(j,4)rep(k,4){res+=dp[n][i][j][k];res%=mod;}
  cout<<res<<endl;



  return 0;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define EPS (1e-10)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

struct st{int a,b,c;};
signed main(){
	int l;cin>>l;l--;
	vector<st>v;
	for(int i=2;i<=19;i++){
		v.push_back({i,i+1,1<<(19-i)});
		v.push_back({i,i+1,0});
	}
	for(int i=18;i>=0;i--){//下から何bit目で0にするか
		if(!(l>>i&1))continue;
		int a=l&~((1<<(i+1))-1);
		v.push_back({1,20-i,a});
	}
	if(l>>19&1){
		v.push_back({1,2,1<<18});
		v.push_back({1,2,0});
	}
	v.push_back({1,20,l});
	cout<<20<<' '<<v.size()<<endl;
	for(auto s:v){
		cout<<s.a<<' '<<s.b<<' '<<s.c<<endl;
	}
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;
struct
{
	char name[13];
	int time;
}mission[100010];
int main(void)
{
	int n, limit;

	while (scanf("%d%d", &n, &limit) != EOF)
	{
		int sum = 0, head = 0, tail = 0;

		for (int i = 0; i < n; i++)
		{
			cin >> mission[i].name;
			scanf("%d", &mission[i].time);
			tail++;
		}
		while (head != tail)
		{
			if (tail == n + 1)
				tail = 0;
			else if (head == n + 1)
				head = 0;
			else
			{
				if (mission[head].time <= limit)
				{
					sum += mission[head].time;
					printf("%s %d\n", mission[head].name, sum);
					head++;
				}
				else
				{
					sum += limit;
					mission[head].time -= limit;
					mission[tail++] = mission[head++];
				}
			}
		}
	}
	//system("pause");

	return 0;
}


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

bool isPalindromic(const int num){
  int pre = num/1000; // 先頭2桁の10進数表現
  int suf = num%100; // 最終2桁の10進数表現
  return ((pre/10)==(suf%10) && (pre%10)==(suf/10));
}

int main(){
  int A, B;
  cin >> A >> B;
  if(A<10000 || A>99999 || B<10000 || B>99999){
    return 0;
  }
  int count = 0;
  for(int i=A; i<=B; ++i){
    if(isPalindromic(i)){
      count++;
    }
  }
  cout << count << endl;
}

Measured memory_bytes: 256
import sys
write = sys.stdout.write

B, W = map(int, sys.stdin.readline().split())
MOD = 10**9 + 7

L = B+W
fact = [1]*(L+1)
rfact = [1]*(L+1)
for i in range(L):
    fact[i+1] = r = fact[i] * (i+1) % MOD
rfact[L] = pow(fact[L], MOD-2, MOD)
for i in range(L, 0, -1):
    rfact[i-1] = rfact[i] * i % MOD

rev2 = pow(2, MOD-2, MOD)

p = q = 0

L = min(B, W)
r2 = "%d\n" % rev2
for i in range(L):
    write(r2)
base = pow(rev2, L-1, MOD)

rB = rfact[B-1]; rW = rfact[W-1]
for i in range(L, B+W):
    base = rev2 * base % MOD
    if i >= B:
        p = (p + (fact[i-1]*rfact[i-B] % MOD) * (rB * base % MOD) % MOD) % MOD
    if i >= W:
        q = (q + (fact[i-1]*rfact[i-W] % MOD) * (rW * base % MOD) % MOD) % MOD
    write("%d\n" % ((1-p+q)*rev2 % MOD))

Measured memory_bytes: 20852
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
#define rep(i,n) for (ll i=0;i<(n);++i)
#define rep2(i,a,b) for (ll i=(a);i<(b);++i)
#define debug(x) cout << #x << '=' << x << endl
#define all(v) (v).begin(),(v).end()
const ll MOD=1e9+7;
//const ll MOD=998244353;
const ll INF=1e9;
const ll IINF=1e18;
const double EPS=1e-8;
const double pi=acos(-1);

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;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    while(cin >> n,n){
        set<int> T,H;
        rep(i,n){
            int t; cin >> t;
            T.insert(t);
        }
        rep(i,2*n) if (!T.count(i+1)) H.insert(i+1);
        int cntt=n,cnth=n,next=0;
        while(cntt>0&&cnth>0){
            auto itrt=T.upper_bound(next);
            if (itrt==T.end()) next=0;
            else --cntt,next=*itrt,T.erase(*itrt);
            if (cntt==0) break;
            auto itrh=H.upper_bound(next);
            if (itrh==H.end()) next=0;
            else --cnth,next=*itrh,H.erase(*itrh);
        }
        cout << cnth << endl << cntt << endl;
    }
}


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

#define rep(i, N) for (int i = 0; i < N; i++)
#define pb push_back
typedef long long ll;
typedef pair<int, int> i_i;
typedef pair<double, int> d_i;

struct bit {
	vector<ll> v;
	bit(int n) : v(n + 1) {}
	ll sum(int i) {
		ll res = 0;
		for (; i > 0; i -= i & -i) res += v[i];
		return res;
	}
	void add(int i, ll x) {
		for (i++; i < v.size(); i += i & -i) v[i] += x;
	}
	int lower_bound(ll x) {
		if (x <= 0) return 0;
		int res = 0;
		for (int i = 1 << 24; i > 0; i >>= 1)
			if (res + i < v.size() && v[res + i] < x) {
				res += i; x -= v[res];
			}
		return res + 1;
	}
};

double solve(int N, vector<int> a, vector<int> b, vector<int> c) {
	ll tot = (ll)N * (N - 1) / 2;
	vector<d_i> di(N);
	rep(i, N) di[i] = d_i((double)a[i] / b[i], i);
	sort(di.begin(), di.end());
	vector<int> _a(N), _b(N), _c(N);
	rep(i, N) {
		int j = di[i].second;
		_a[i] = a[j], _b[i] = b[j], _c[i] = c[j];
	}
	a = _a, b = _b, c = _c;
	double lb = -1e9, ub = 1e9;
	rep(t, 100) {
		double x0 = (lb + ub) / 2;
		vector<d_i> di(N);
		rep(i, N) di[i] = d_i((c[i] - a[i] * x0) / b[i], i);
		sort(di.begin(), di.end());
		bit bt(N);
		ll sum = 0;
		rep(j, N) {
			int i = di[j].second;
			sum += j - bt.sum(i);
			bt.add(i, 1);
		}
		if (sum * 2 >= tot) ub = x0;
		else lb = x0;
	}
	return lb;
}

int main() {
	int N; cin >> N;
	vector<int> a(N), b(N), c(N);
	rep(i, N) scanf("%d%d%d", &a[i], &b[i], &c[i]);
	double x = solve(N, a, b, c);
	swap(a, b);
	double y = solve(N, a, b, c);
	printf("%.15f %.15f\n", x, y);
}


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

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

    int max_profit = numeric_limits<int>::min();
    int min_value = numeric_limits<int>::max();

    for (int x; n-- && cin >> x;) {
        max_profit = max(x - min_value, max_profit);

        if (x < min_value)
            min_value = x;
    }

    cout << max_profit << endl;

    return 0;
}

Measured memory_bytes: 1160
def ramp(t):
    if t >= 0:
        return t
    else:
        return 0
def heav(t):
    if t >= 0:
        return(1)
    else:
        return(0)
N,W = map(int,input().strip().split(" "))
lst = []
for i in range(N):
    l = list(map(int,input().strip().split(" ")))
    lst.append(l)
table = [[0 for c in range(W+1)] for i in range(N+1)]
for i in range(1,N+1):
    for c in range(1,W+1):
        table[i][c] = max(table[i-1][c],table[i-1][ramp(c-lst[i-1][1])]+lst[i-1][0]*heav(c-lst[i-1][1]))
print(table[N][W])


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

long NumberOfPackage(vector<int>& W, int k, int P)
{
    int j = 0;
    for (int i = 0; i < k; ++i) {
        int p = 0;
        while (j < W.size() && p + W[j] <= P) {
            p += W[j];
            ++j;
        }
    }
    return j;
}

int search(vector<int> W, int k)
{
    int low = 1;
    int high = 0;
    for (auto w : W) {
        high += w;
    }
    while (low < high) {
        int mid = (low + high) / 2;
        long n = NumberOfPackage(W, k, mid);
        if (n < W.size()) {
            low = mid + 1;
        } else if (n == W.size()) {
            high = mid;
        }
    }
    return high;
}

int main()
{
    int n, k;
    cin >> n >> k;

    vector<int> W;
    for (int i = 0; i < n; ++i) {
        int w;
        cin >> w;
        W.push_back(w);
    }
    cout << search(W, k) << endl;
}


Measured memory_bytes: 3896
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <string>
#include <iomanip>
# define M_PIl        3.141592653589793238462643383279502884
#define faster       ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

typedef long long ll;
typedef long double ld;

int main(){
  ll n; cin >> n;
  vector<ll> arr(n);
  map<ll,ll> m;
  for(ll i=0;i<n;i++){
    cin >> arr[i];
    if((i+arr[i])<=n){
      m[i+arr[i]]++;
    }
  }
  ll ans=0;
  for(ll i=0;i<n;i++){
    if(i-arr[i]>0){
      ans+=m[i-arr[i]];
    }
  }
  cout << ans;
}

Measured memory_bytes: 15184
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <sstream>
#include <functional>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <list>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<P,ll> PPI;
typedef pair<ll,P> PIP;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<P> vp;
#define PQ(T) priority_queue<T,vector<T>,greater<T>>
#define PQ2(T) priority_queue<T>
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const ll INF = 1LL<<29;
const ll mod = 1e9+7;
#define REP(i,a,b) for(ll (i)=a;(i)<(ll)(b);++(i))
#define rep(i,n) REP(i,0,n)
#define rep1(i,n) REP(i,1,n+1)
#define repd(i,n,d) for(ll (i)=0;(i)<(ll)(n);(i)+=(d))
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset((m),(v),sizeof(m))
#define chmin(x,y) ((x)=min((x),(y)))
#define chmax(x,y) ((x)=max((x),(y)))
#define fst first
#define snd second
#define UNIQUE(x) (x).erase(unique(all(x)),(x).end())
#define DEBUG(x) cerr<<"line ("<<__LINE__<<")  "<<#x<<": "<<x<<endl;
template<class T> ostream &operator<<(ostream &os, const vector<T> &v){int n=v.size();rep(i,n)os<<v[i]<<(i==n-1?"":" ");return os;}

int main(){
	ll n;
	cin>>n;
	vector<ll> a(1<<n);
	rep(i, 1<<n) cin>>a[i];
	while(a.size()>1){
		vector<ll> b;
		for(int i = 0; i < a.size(); i+=2){
			ll x = a[i], y = a[i+1];
			if(x==y) b.pb(x);
			else b.pb(abs(x-y));
		}
		a.swap(b);
	}
	cout<<a[0]<<endl;
	return 0;
}


Measured memory_bytes: 3448
def get_input():
    while True:
        try:
            yield ''.join(input())
        except EOFError:
            break

students = ["" for i in range(51)]

N = list(get_input())
for l in range(len(N)):
    data = N[l].split(",")
    num = int(data[0])
    t = data[1]
    students[num] = t

A,B,AB,O = 0,0,0,0
for i in range(1,51):
    if students[i] == "A":
        A += 1
    elif students[i] == "AB":
        AB += 1
    elif students[i] == "B":
        B += 1
    elif students[i] == "O":
        O += 1
print(A)
print(B)
print(AB)
print(O)




Measured memory_bytes: 5596
import java.util.Scanner;


public class Main {

    public static void main(String[] args) {

    	Main main=new Main();

    	main.run();

    }

    void run() {

    	Scanner sc=new Scanner(System.in);


    	int A=sc.nextInt();
    	int B=sc.nextInt();

    	if(A%B==0) {
    		System.out.println("-1");
    	}else {
    		System.out.println(A);
    	}

    }
}



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

using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define INF LONG_MAX
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.end(),a.begin()
#define rep(i,N) for(int i=0;i<N;i++)

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

  int H,N;
  cin>>H>>N;
  vector<int>A(N),B(N);
  for(int i=0;i<N;i++)cin>>A[i]>>B[i];
  vector<vector<ll>>dp(N+1,vector<ll>(H+10001,INT_MAX));
  dp[0][0]=0;
  for(int i=1;i<=N;i++){
    for(int j=0;j<=H+10000;j++){
      dp[i][j]=min(dp[i][j],dp[i-1][j]);
      if(j-A[i-1]>=0)dp[i][j]=min(dp[i-1][j],dp[i][j-A[i-1]]+B[i-1]);
    }
  }
  ll ans=LONG_MAX;
  for(int i=H;i<=H+10000;i++){
    ans=min(dp[N][i],ans);
  }
  cout<<ans<<endl;
  return 0;
}



Measured memory_bytes: 160640
#include <stdio.h>

int main(){

	int i,a, b,c,tmp;

	scanf("%d%d%d", &a, &b, &c);
	for( i=0;i<2;i++){
		if (a > b){
			tmp = a;
			a = b;
			b = tmp;
		}
		if (b > c){
			tmp = b;
			b = c;
			c = tmp;
		}
	}
	printf("%d %d %d\n", a, b, c);

	return 0;
}

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

int main()
{
  int n;
  cin >> n;
  vector<int> vec(n);
  for (int i = 0; i < n; i++)
  {
    cin >> vec.at(i);
  }

  int answer = 0;
  for (int i = 1; i < n - 1; i++)
  {
    int p1 = vec.at(i - 1);
    int p2 = vec.at(i);
    int p3 = vec.at(i + 1);

    int minP = min(p1, min(p2, p3));
    int maxP = max(p1, max(p2, p3));
    if (p2 != minP && p2 != maxP)
    {
      answer++;
    }
  }

  cout << answer << endl;
}


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

int main() {
	int a,b;
  	cin>>a>>b;
  
  	if(a%3==0 || b%3==0 || (a+b)%3==0){
    	cout<<"Possible"<<endl;
    }else{
    	cout<<"Impossible"<<endl;
    }
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
using namespace std;
int Tsukasa[1000];  //parent
int Hizikata[1000]; //left-child
int Yuuma[1000];    //right-child  May Be Yuma
bool used[1000];
int counter=0,n,Pos;
bool finfin=false;

void Init(int n){
  for(int i=0;i<n;i++){
    Tsukasa[i]=-1;
    Hizikata[i]=-1;
    Yuuma[i]=-1;
    used[i]=false;
  }
}

int SRoot(int n){ // root search
  for(int i=0;i<n;i++)if(Tsukasa[i] == -1)return i;
  return -2;
}

void Print(int s){ // print s and count number of used node
  printf("%d",s);
  counter++;
  if(counter != n)printf(" ");
  used[s]=true;
}
void BInit(int n){ // init of array
  for(int i=0;i<n;i++){
    used[i] = false;
  }
}

int Pre(int s){ // Preorder
  if(s!= -1){
    Print(s);
    Pre(Hizikata[s]);
    Pre(Yuuma[s]);
  }
}


int In(int s){ // Inorder
  if(s != -1){
    In(Hizikata[s]);
    Print(s);
    In(Yuuma[s]);
  }
}

int Po(int s){ //Postorder
  if(s != -1){
    Po(Hizikata[s]);
    Po(Yuuma[s]);
    Print(s);
  }
}

int main(){ // most important function. perhaps we cannot take "accepted" without this.
  int id,lef,rig,rn;
 
  scanf("%d\n",&n);
 
  Init(n); 
  rn = n;
  while(rn-- > 0){
    scanf("%d %d %d\n",&id,&lef,&rig);
    Tsukasa[lef] = Tsukasa[rig] = id;
    Hizikata[id] = lef;
    Yuuma[id] = rig;
  }
  // Tsukasa-array is used to store datas about parent
  // if node doesnt have parent, it is -1
 
  printf("Preorder\n");
  counter=0;
  printf(" ");
  Pre(SRoot(n));
  printf("\n");

  BInit(n);
  counter=0;
  printf("Inorder\n");
  printf(" ");
  In(SRoot(n));
  printf("\n");

  BInit(n);
  counter=0;
  printf("Postorder\n");
  finfin=false;
  BInit(n);
  printf(" ");
  Po(SRoot(n));
  printf("\n");
  return 0;
}

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

int main(void){
int a;
cin >> a;
if(a%10 == 3){
	cout << "bon" << endl;
}else if(a%10==0||a%10==1||a%10==6||a%10==8){
	cout << "pon" << endl;
}else{
	cout << "hon" << endl;
}
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define isYES(x) printf("%s\n",(x) ? "YES" : "NO")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define isYes(x) printf("%s\n",(x) ? "Yes" : "No")
#define isIn(x,y,h,w) (x >= 0 && x < h && y >= 0 && y < w)

#define int long long
//using ll = long long;
using P = pair<int,int>;

ostream &operator<<(ostream &os,const P &p){ return os << "(" << p.first << "," << p.second << ")"; }

template<class T> T &chmin(T &a,const T &b){ return a = min(a,b); }
template<class T> T &chmax(T &a,const T &b){ return a = max(a,b); }
 
const int INF=1e+18;
const double EPS=1e-9;
const int MOD=1000000007;

const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

signed main(){
	int n,ans = 0,cnt = 1;
	cin >> n;
	for(int i = 0;i < n;i++){
		int a;
		cin >> a;
		if(a == cnt){
			cnt++;
		}else{
			ans++;
		}
	}
	if(cnt == 1) cout << -1 << endl;
	else cout << ans << endl;
}

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

typedef pair<string, int> P;
typedef pair<int, P> K;

bool compare_by_b(K a, K b) {
    if(a.second.first != b.second.first){
        return a.second.first < b.second.first;
    }else{
        return a.second.second > b.second.second;    
    }
}

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

    vector<K> p;
    vector<int> cou;
    for(int i = 0; i < N; i++){
        int a;
        string b;
        P c;
        K d;
        cin >> b >> a;
        c.first = b;
        c.second = a;
        d.first = i + 1;
        d.second = c;
        p.push_back(d);
    }

    sort(p.begin(), p.end(), compare_by_b);

    for(int i = 0; i < N; i++){
        cout << p[i].first << endl;
    }

    /*string j = "";

    vector<int> ans;

    for(int i = 0; i < N; i++){
        if(j != p[i].second.first){
            j = p[i].second.first;
            ans.push_buck(p[i].first);
        }else{
            if(p[i].second.second >= p[i - 1].second.second){

            }else{

            }
        }
    }*/



}

Measured memory_bytes: 256
void main(){
  import std.stdio, std.string, std.conv, std.algorithm;

  int n, m; rd(n, m);
  struct Seq{int l, r;}
  auto seqs=new Seq[](m);
  foreach(i; 0..m) rd(seqs[i].l, seqs[i].r);

  sort!((a, b)=>(a.r==b.r ? a.l<b.l : a.r<b.r))(seqs);
  int last=0, need=0; // last -> last+1
  foreach(seq; seqs){
    if(seq.l<=last && last<=seq.r) continue;
    last=seq.r-1;
    need++;
  }
  writeln(need);

}

void rd(T...)(ref T x){
  import std.stdio, std.string, std.conv;
  auto l=readln.split;
  assert(l.length==x.length);
  foreach(i, ref e; x) e=l[i].to!(typeof(e));
}

Measured memory_bytes: 4092
#include <stdio.h>

int main(int argc, char const *argv[]) {
  int x=0,y=0;
  int ans=0;
  scanf("%d %d",&x,&y);
  for (int i = 0; i < 2; i++) {
    if (x>y) {
      ans+=x;
      x--;
    }else{
      ans+=y;
      y--;
    }
  }
  printf("%d\n",ans);
  return 0;
}


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

template <class Abel> struct BIT {
    vector<Abel> dat[2];
    Abel UNITY_SUM = 0;                     // to be set

    /* [1, n] */
    BIT(int n) { init(n); }
    void init(int n) { for (int iter = 0; iter < 2; ++iter) dat[iter].assign(n + 1, UNITY_SUM); }

    /* a, b are 1-indexed, [a, b) */
    inline void sub_add(int p, int a, Abel x) {
        for (int i = a; i < (int)dat[p].size(); i += i & -i)
            dat[p][i] = dat[p][i] + x;
    }
    inline void add(int a, int b, Abel x) {
        sub_add(0, a, x * -(a - 1)); sub_add(1, a, x); sub_add(0, b, x * (b - 1)); sub_add(1, b, x * (-1));
    }

    /* a is 1-indexed, [a, b) */
    inline Abel sub_sum(int p, int a) {
        Abel res = UNITY_SUM;
        for (int i = a; i > 0; i -= i & -i) res = res + dat[p][i];
        return res;
    }
    inline Abel sum(int a, int b) {
        return sub_sum(0, b - 1) + sub_sum(1, b - 1) * (b - 1) - sub_sum(0, a - 1) - sub_sum(1, a - 1) * (a - 1);
    }

    /* debug */
    void print() {
        for (int i = 1; i < (int)dat[0].size(); ++i) cout << sum(i, i + 1) << ",";
        cout << endl;
    }
};

int main() {
    int N, Q; cin >> N >> Q;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];

    vector<int> lefts(Q), rights(Q), ids(Q);
    for (int i = 0; i < Q; ++i) {
        cin >> lefts[i] >> rights[i];
        --lefts[i];
        ids[i] = i;
    }
    sort(ids.begin(), ids.end(), [&](int i, int j) {
        return rights[i] < rights[j]; });

    BIT<int> bit(N + 5);
    vector<int> prev(1100000, -1);
    vector<int> res(Q, 0);
    int r = 0;
    for (auto i : ids) {
        for (; r < rights[i]; ++r) {
            bit.add(prev[a[r]] + 2, r + 2, 1);
            prev[a[r]] = r;
        }
        int tmp = bit.sum(lefts[i] + 1, lefts[i] + 2);
        res[i] = max(res[i], tmp);
    }
    for (int i = 0; i < Q; ++i) cout << res[i] << endl;
}

Measured memory_bytes: 21732