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

int div(int a);
int main() {
    int ans=0,N,A,tmp;
    cin >> N;
    cin >> A;
    ans=div(A);
    for(int i=0;i<N-1;i++){
        cin >> A;
        tmp=div(A);
        if(tmp<ans){
            ans=tmp;
        }
    }
    cout << ans << endl;
}
int div(int a){
    int num=0;
    while(a%2==0){
        a/=2;
        num++;
    }
    return num;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

ll N, W;
ll w[110], v[110];
ll dp[110][100010];

int main()
{
	cin >> N >> W;
	for (int i = 0; i < N; i++)
	{
		cin >> w[i] >> v[i];
	}

	for (int j = 0; j <= W; j++)
	{
		dp[0][j] = 0;
	}

	for (int i = 1; i <= N; i++)
	{
		for (int j = 0; j <= W; j++)
		{
			//突っ込める
			if (j - w[i - 1]>= 0)
			{
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
				
			}
			else
			{
				dp[i][j] = dp[i - 1][j];
			}
//			cout << dp[i][j];
//			cout << " ";
		}
//		cout << endl;
	}

	cout << dp[N][W] << endl;
}

Measured memory_bytes: 80128
program yet_another_palindrome_partitioning
  implicit none
  integer, parameter :: infty = 1e9
  integer :: n, a(200000), h(0:200000), x, i, j
  integer :: opt(0:200000), dp(0:2**26-1)
  character(200000) :: s
  a = 0
  h = 0
  opt = 0
  dp = infty
  read(*,*) s
  s = trim(adjustl(s))
  n = len_trim(s)
  do i = 1, n
    a(i) = ichar(s(i:i))-97
    h(i) = xor(h(i-1),lshift(1,a(i)))
  end do
  do i = 1, n
    dp(h(i-1)) = min(dp(h(i-1)),opt(i-1))
    opt(i) = dp(xor(h(i),0))+1
    do j = 0, 25
      x = lshift(1,j)
      opt(i) = min(opt(i),dp(xor(h(i),x))+1)
    end do
  end do
  write(*,'(i0)') opt(n)
  stop
end program yet_another_palindrome_partitioning

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

class Cube{
public:
	int f[6];

	Cube(){}
	void roll_z(){ roll(1, 2, 4, 3); } //
	void roll_y(){ roll(0, 2, 5, 3); } // to W
	void roll_x(){ roll(0, 1, 5, 4); } // to N
	void roll(int i, int j, int k, int l){
		int t = f[i]; f[i] = f[j]; f[j] = f[k]; f[k] = f[l]; f[l] = t;
	}
};

bool eq(Cube c1, Cube c2){
 for(int i = 0; i < 6; i++)
  if(c1.f[i] != c2.f[i] ) return false;
 return true;
}

bool equal(Cube c1, Cube c2){
	for (int i = 0; i < 6; i++){
		for (int j = 0; j < 4; j++){
			if (eq(c1, c2))
				return true;
			c1.roll_z();
		}
		if (i % 2 == 0) c1.roll_y();
		else c1.roll_x();
	}
	return false;
}

int main(){
	Cube c1, c2;

	for (int i = 0; i < 6; i++) cin >> c1.f[i];
	for (int i = 0; i < 6; i++) cin >> c2.f[i];

        if(equal(c1, c2)) cout << "Yes" << endl;
        else cout << "No" << endl;

	return 0;
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
int main(){
	#ifndef ONLINE_JUDGE
    // for getting input from input.txt
    freopen("input.txt", "r", stdin);
    // for writing output to output.txt
    freopen("output.txt", "w", stdout);
#endif
       ios_base::sync_with_stdio(false);
       cin.tie(0);
   
    int n, cnt= 0;
    cin >> n;
    int a[n];
    for(int i =0 ;i<n; i++){ 
    	cin >> a[i];
 }
    sort(a,a+n);
 
    for(int i = 0; i < n; i++){
        for(int j = i+1; j<n; j++){
            for(int k = j+1; k<n; k++){
                cnt += a[i]+a[j] > a[k];
            }
        }
    }
                    
    cout << cnt << endl;  
    }  

Measured memory_bytes: 3588
#include<bits/stdc++.h>
using ll = long long;

int main()
{
    std::map<int,int> map;
    int a,b,c; std::cin >> a >> b >> c;
    bool res = false;
    if(a == b && b != c && a != c)res = true;
    if(b == c && a != b && a != c)res = true;
    if(a == c && a != b && c != b)res = true;
    std::cout << (res ? "Yes" : "No") << std::endl;
}

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

using namespace std;

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

    vector<string> lines(n);
    for (int i = 0; i < n; i++) {
        cin >> lines[i];
    }

    for (int i = 0; i < m + 2; i++) cout << '#';
    cout << endl;
    for (int i = 0; i < n; i++) {
        cout << '#' << lines[i] << '#' << endl;
    }
    for (int i = 0; i < m + 2; i++) cout << '#';
    cout << endl;

    return 0;
}


Measured memory_bytes: 256
program abc113c
    use,intrinsic :: iso_fortran_env
    implicit none
    type ken
        integer(int32), allocatable:: si(:), year(:)
        integer(int32):: i=0
    end type
    integer(int32):: n,m,i,np,ny,j
    integer(int32), allocatable:: ip(:), iy(:), cnt(:), num(:,:)
    type(ken), allocatable:: p(:)


    read*, n,m
    allocate(p(n),cnt(n))
    allocate(ip(m),iy(m), num(2,m))
    cnt(:) = 0
    do i=1,m
        read*, ip(i), iy(i)
        cnt(ip(i))=cnt(ip(i))+1
    end do

    do i=1,n
        allocate(p(i)%si(cnt(i)))
        allocate(p(i)%year(cnt(i)))
    end do

    do i=1,m
        np = ip(i)
        ny = iy(i)
        p(np)%i=p(np)%i+1
        p(np)%si(p(np)%i)=i
        p(np)%year(p(np)%i)=ny
    end do

    do i=1,n
        if (cnt(i) == 0) cycle
        call double_sort(p(i)%year, p(i)%si, 1, cnt(i))
    end do

    do i=1,n
        if (cnt(i) == 0) cycle
        do j=1,cnt(i)
            num(1,p(i)%si(j)) = i
            num(2,p(i)%si(j)) = j
        end do
    end do

    do i=1,m
        print'(2(i0.6))', num(:,i)
    end do
contains

recursive subroutine double_sort(ar1, ar2, fst, lst)
    integer(int32),intent(inout):: ar1(:),ar2(:)
    integer(int32),intent(in):: fst,lst
    integer(int32):: mdl

    if (lst - fst < 2) then
        if (ar1(fst) > ar1(lst)) then
            call swap(ar1(fst), ar1(lst))
            call swap(ar2(fst), ar2(lst))
        end if
        return
    end if

    mdl = (fst+lst)/2

    call double_sort(ar1,ar2,fst,mdl)
    call double_sort(ar1,ar2,mdl+1,lst)
    call double_merge_(ar1,ar2,fst,mdl,lst)
end subroutine


subroutine double_merge_(ar1,ar2,fst,mdl,lst)
    integer(int32),intent(inout):: ar1(:),ar2(:)
    integer(int32),intent(in):: fst,mdl,lst
    integer(int32),allocatable:: t1(:),t2(:)
    integer(int32):: li,ri,ti

    allocate(t1(lst-fst+1), t2(lst-fst+1))

    li=fst
    ri=mdl+1
    ti=1

    do while(li <= mdl .and. ri <= lst)
        if (ar1(li) <= ar1(ri)) then
            t1(ti) = ar1(li) 
            t2(ti) = ar2(li)
            li=li+1
        else
            t1(ti) = ar1(ri)
            t2(ti) = ar2(ri)
            ri=ri+1
        end if
        ti=ti+1
    end do

    if (li <= mdl) then
        t1(ti:) = ar1(li:mdl)
        t2(ti:) = ar2(li:mdl)
    else
        t1(ti:) = ar1(ri:lst)
        t2(ti:) = ar2(ri:lst)
    end if

    ar1(fst:lst) = t1(:)
    ar2(fst:lst) = t2(:)

    deallocate(t1,t2)
end subroutine


subroutine swap(x,y)
    integer(int32),intent(inout):: x,y
    integer(int32):: tmp
    tmp = x
    x = y
    y = tmp
end subroutine




end program abc113c

Measured memory_bytes: 20696
#include <bits/stdc++.h>
using namespace std;
#define P pair<int,int>
#define ll long long
const int N = 200+10;
char s[N];
int n,k;
ll dp[N][4];//dp[N][k]N个0有多少个k个不是0的数
int main()
{
    scanf("%s",s+1);
    scanf("%d",&k);
    n=strlen(s+1);
    //dp[0][1]=1;
    for(int i=1;i<=n;i++)
    {
        dp[i][1]=dp[i-1][1]+9;
    }
    for(int i=2;i<=n;i++)
    {
        for(int j=2;j<=3;j++)
        {
            dp[i][j]=dp[i-1][j]+dp[i-1][j-1]*9;
        }
    }
    for(int i=0;i<=n;i++)
    {
        dp[i][0]=1;
    }
    //cout<<dp[n][k]<<"\n";
    ll num=k;
    ll ans=0;
    for(int i=1;i<=n&&num;i++)
    {
        if(s[i]=='0')
            continue;
        if(num==1)
            ans+=(s[i]-'0')*dp[n-i][num-1]+dp[n-i][num];
        else
            ans+=(s[i]-'0'-1)*dp[n-i][num-1]+dp[n-i][num];
//        cout<<ans<<" "<<num<<"\n";
        num--;
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 256
from collections import defaultdict, deque
import sys
import heapq
import bisect
import math
import itertools
import string
import queue
import copy
import time
# import numpy as np
from fractions import gcd

sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7

def inp(): return int(sys.stdin.readline())
 
def inp_list(): return list(map(int, sys.stdin.readline().split()))

def lcm(x, y): return (x * y) // gcd(x, y)

n = inp()
ans = 0
for i in range(1, n + 1):
    if i % 3 == 0 and i % 5 == 0: continue
    if i % 3 == 0: continue
    if i % 5 == 0: continue
    ans += i
print(ans)

Measured memory_bytes: 10992
#include<iostream>
#include<string>

using namespace std;

int main(){

  string in;
  int data[4];

  while(cin >> in){

    for(int i = 0; i < 4; i++) data[i] = 0;
    
    for(int i = 0; i < in.length(); i++){
      if(in[i] == 'K') data[0]++;
      if(in[i] == 'U') data[1]++;
      if(in[i] == 'P') data[2]++;
      if(in[i] == 'C') data[3]++;
    }

    int min = 400;

    for(int i = 0; i < 4; i++){
      if(min > data[i]) min = data[i];
    }
    cout << min << endl;
  }
  return 0;
}

Measured memory_bytes: 0
# -*- coding: utf-8 -*-
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

x, y = map(int,input().split())
ans = [x]
while ans[-1] < y:
    ans.append(ans[-1] * 2)
    #print(ans)
if ans[-1] > y:
    print(len(ans) - 1)
else:
    print(len(ans))


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define ALL(x) (x).begin(), (x).end()
#define REP(i ,n) for(int i = 0; i < (int)(n); i++)
#define pb push_back
typedef vector<int>vint;
typedef vector<ll>vll;
template<typename T> istream &operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}
int main()
{
    int a,p;
    cin >> a >> p;
    cout << ((a*3+p)/2) << endl;
}

Measured memory_bytes: 3644
def main():
    from sys import stdin
    def input():
        return stdin.readline().strip()

    # return max({i | i*i < a*b})
    # binary search
    def square_range(a, b):
        left = a
        right = b - 1
        while left < right:
            center = (left + right + 1) // 2
            if center * center < a * b:
                left = center
            else:
                right = center - 1
        return left

    q = int(input())
    ans = [0] * q

    for lap in range(q):
        a, b = map(int, input().split())

        if a < b:
            mid = square_range(a, b)
        else:
            mid = square_range(b, a)

        if mid * (mid + 1) < a * b:
            ans[lap] = (2 * mid - 1)
        else:
            ans[lap] = (2 * mid - 2)
    
    for i in ans:
        print(i)

main()

Measured memory_bytes: 64664
#include<iostream>
#include<bits/stdc++.h>
#define ll long long
#define faltu ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
const int maxn=200005;
ll bit[4*maxn],mark[maxn*4];
ll a[maxn];
ll n,m;
ll oper(ll x,ll y)
{
    return min(x,y);
}
void build(ll int l,ll int r,ll int ind)
{
    if(l==r)
    {
        bit[ind]=0;
        return;
    }
    ll int mid=(l+r)/2;
    build(l,mid,ind*2ll);
    build(mid+1,r,ind*2ll+1ll);
    //bit[ind]=oper(bit[ind*2ll],bit[ind*2ll+1]);
}
void push(ll int l,ll int tl,ll int mid,ll int ind)
{
    if(mark[ind]==false)return;
    mark[ind*2ll]=mark[ind*2ll+1]=true;
    mark[ind]=false;
    bit[ind*2ll]=bit[ind];
    bit[ind*2ll+1]=bit[ind]+mid-l+1;
}
void update(ll int l,ll int r,ll int ind,ll int tl,ll int tr,ll int val)
{
    if(l>tr||r<tl)return ;
    if(l>=tl&&r<=tr)
    {
        bit[ind]=val+l-tl;
        mark[ind]=true;
        return;
    }
    int mid=(l+r)/2ll;
    push(l,tl,mid,ind);
    update(l,mid,ind*2ll,tl,tr,val);
    update(mid+1,r,ind*2ll+1,tl,tr,val);
    bit[ind]=oper(bit[ind*2ll],bit[ind*2ll+1ll]);
    mark[ind]=false;
}
ll int query(ll int l,ll int r,ll ind,ll int tl,ll int tr)
{
    if(l>tr||r<tl)return -1;
    if(l>=tl&&r<=tr)
    {
        return bit[ind];
    }
    if(mark[ind]==true)return bit[ind]+tl-l;
    ll int mid=(l+r)/2;
    push(l,tl,mid,ind);
    ll int xx=query(l,mid,ind*2ll,tl,tr);
    ll int yy=query(mid+1,r,ind*2ll+1ll,tl,tr);
    if(xx!=-1)return xx;
    else return yy;
    return oper(xx,yy);
}
int main()
{
    faltu;
    int t=1;
    //cin>>t;
    while(t--)
    {
        cin>>n>>m;
        build(1,m,1);
        for(int i=1;i<=n;i++)
        {
            int l,r;
            cin>>l>>r;
            int val=1e9;
            if(l!=1)val=query(1,m,1,l-1,l-1);
            val++;
            update(1,m,1,l,r,val);
            int ans=bit[1]+i;
            if(ans>=1e9)ans=-1;
            cout<<ans<<endl;
        }
    }
}

Measured memory_bytes: 11784
using System;
using System.Linq;
using static System.Math;
using static System.Console;

namespace atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            Stdin io = new Stdin();
            Solve(io);
        }
        static void Solve(Stdin io)
        {
            long x = io.Input();
            WriteLine((x<1200)?"ABC":"ARC");
        }
    }
    class Stdin
    {
        public long Input()
        {
            return long.Parse(ReadLine());
        }
        public long[] Inputs()
        {
            string[] buf = ReadLine().Split(' ');
            return buf.Select(x => long.Parse(x)).ToArray();
        }
        public string Raw_Input()
        {
            return ReadLine();
        }
    }
}


Measured memory_bytes: 11092
#include<stdio.h>

int main()
{
int a,b,c,d;
while(1){
scanf("%d %c %d",&a,&c,&b);
if(c=='+'){
d=a+b;
}else if(c=='-'){
d=a-b;
}else if(c=='*'){
d=a*b;
}else if(c=='/'){
d=a/b;
}else break;

printf("%d\n",d);
}
return 0;
}

Measured memory_bytes: 600
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
time = 0
t1 = [a, b, c, d, e]
t2 = []

i = 0
while i <= 4:
    if t1[i]%10 != 0:
        tmp = 10-t1[i]%10
        t2.append([10 - t1[i]%10, i]) #[10に足りない分, i]
    else:
        t2.append([t1[i]%10, i]) #[0, i]
    i += 1

#10の倍数に近い順にソート
t3 = sorted(t2)


for i in range(4):
    if t3[i][0] == 0:
        time += t1[t3[i][1]]
    else:
        time += t1[t3[i][1]] + t3[i][0]

time += t1[t3[-1][1]]

print(time)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define li long long
int n;
struct edge{
	int to,nxt;
}e[1010];
int cnt,fir[1010];
void ins(int u,int v){
	e[++cnt].to = v;e[cnt].nxt = fir[u];fir[u] = cnt;
	e[++cnt].to = u;e[cnt].nxt = fir[v];fir[v] = cnt;
}
int dpt[1010];
int mx,gen,ge;
bool ed[110][110];
void dfs(int q,int lst){
	dpt[q] = dpt[lst] + 1;
	if(dpt[q] > mx){
		mx = dpt[q];
		gen = q;
	}
	for(int i = fir[q];i;i = e[i].nxt){
		int j = e[i].to;
		if(j == lst) continue;
		dfs(j,q);
	}
}
li ans1,ans2;
int jl[1010],ct;
void dfs2(int q,int lst){
	jl[++ct] = q;
	for(int i = fir[q];i;i = e[i].nxt){
		int j = e[i].to;
		if(j == lst || dpt[j] != dpt[q] - 1) continue;
		dfs2(j,q);
	}
}
int sd[1010],sl[1010];
int mxas[1010];
void dfs3(int q,int lst){
	sd[q] = sd[lst] + 1;
	int ss = 0;
	for(int i = 1;i <= n;++i) if(ed[q][i]){
		if(i == lst) continue;
		++ss;
		dfs3(i,q);
	}
	sl[q] = ss;
}
void work(int q){
	for(int i = 1;i <= n;++i) mxas[i] = sd[i] = sl[i] = 0;
	dfs3(q,0);
	for(int i = 1;i <= n;++i) mxas[sd[i]] = max(mxas[sd[i]],sl[i]);
	ans2 = 1;
	for(int i = 1;i <= ans1;++i) if(mxas[i] >= 1) ans2 *= mxas[i]; 
}
int dp4[1010];
void dfs4(int q,int lst){
	for(int i = fir[q];i;i = e[i].nxt){
		int j = e[i].to;
		if(j == lst) continue;
		dfs4(j,q);
		dp4[q] = max(dp4[q],dp4[j]);
	}
	++dp4[q];
}
int main(){
	int u,v,w,i,j,k;
	cin>>n;
	if(n == 1){
		cout<<"1 1";
		return 0;
	}
	for(i = 1;i < n;++i){
		cin>>u>>v;
		ins(u,v);
		ed[u][v] = ed[v][u] = 1;
	}
	if(n == 2){
		cout<<"1 2";
		return 0;
	}
	dfs(1,0);
	for(i = 1;i <= n;++i) dpt[i] = 0;
	ge = gen;
	mx = 0;
	dfs(gen,0);
	ans1 = mx + 1 >> 1;
	dfs2(gen,0);
	//cout<<gen<<" "<<ge<<endl;
	li ans3 = 9000000000000000000ll;
	if(mx % 2 == 0){
		u = jl[mx / 2];
		v = jl[mx / 2 + 1];
		//cout<<u<<" "<<v<<endl;
		ed[u][v] = ed[v][u] = 0;
		++n;
		ed[n][u] = ed[n][v] = ed[u][n] = ed[v][n] = 1;
		work(n);
		ans3 = ans2;
	}
	else{
		work(jl[mx + 1 >> 1]);
		ans3 = ans2;
		u = jl[mx + 1 >> 1];
		//dfs4(u,0);
		++n;
		ed[n][u] = ed[u][n] = 1;
		//cout<<"***"<<endl;
		for(i = fir[u];i;i = e[i].nxt){
			v = e[i].to;
			//cout<<v<<endl;
			ed[u][v] = ed[v][u] = 0;
			ed[n][v] = ed[v][n] = 1;
			work(n);
			ed[n][v] = ed[v][n] = 0;
			ed[u][v] = ed[v][u] = 1;
			ans3 = min(ans3,ans2);
		}
	} 
	cout<<ans1<<" "<<ans3<<endl;
	return 0;
}


Measured memory_bytes: 384
import java.io.*;
import java.nio.CharBuffer;
import java.util.NoSuchElementException;

public class Main {

    public static void main(String[] args) {
        SimpleScanner scanner = new SimpleScanner(System.in);
        PrintWriter writer = new PrintWriter(System.out);

        final int MOD = 1000000007;
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[] a, b;
        a = new int[n + 1];
        b = new int[m + 1];
        for (int i = 1; i <= n; ++i)
            a[i] = scanner.nextInt();
        for (int j = 1; j <= m; ++j)
            b[j] = scanner.nextInt();
        int[][] g = new int[n + 1][m + 1];
        for (int i = 0; i <= n; ++i)
            g[i][0] = 1;
        for (int j = 0; j <= m; ++j)
            g[0][j] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                g[i][j] = (g[i][j - 1] + g[i - 1][j]) % MOD;
                if (a[i] != b[j])
                    g[i][j] -= g[i - 1][j - 1];
                g[i][j] = (g[i][j] + MOD) % MOD;
            }
        }
        writer.println(g[n][m]);
        writer.close();
    }

    private static class SimpleScanner {

        private static final int BUFFER_SIZE = 10240;

        private Readable in;
        private CharBuffer buffer;
        private boolean eof;

        SimpleScanner(InputStream in) {
            this.in = new BufferedReader(new InputStreamReader(in));
            buffer = CharBuffer.allocate(BUFFER_SIZE);
            buffer.limit(0);
            eof = false;
        }


        private char read() {
            if (!buffer.hasRemaining()) {
                buffer.clear();
                int n;
                try {
                    n = in.read(buffer);
                } catch (IOException e) {
                    n = -1;
                }
                if (n <= 0) {
                    eof = true;
                    return '\0';
                }
                buffer.flip();
            }
            return buffer.get();
        }

        void checkEof() {
            if (eof)
                throw new NoSuchElementException();
        }

        char nextChar() {
            checkEof();
            char b = read();
            checkEof();
            return b;
        }

        String next() {
            char b;
            do {
                b = read();
                checkEof();
            } while (Character.isWhitespace(b));
            StringBuilder sb = new StringBuilder();
            do {
                sb.append(b);
                b = read();
            } while (!eof && !Character.isWhitespace(b));
            return sb.toString();
        }

        int nextInt() {
            return Integer.valueOf(next());
        }

        long nextLong() {
            return Long.valueOf(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}

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

int c[33], s[444][33];
int sco(int t, const vector<int> &v) {
    int r = 0, l = 0, d = v.size();
    for(int i = 0; i < d; i++)
        if(v[i] == t)
            r += s[i][t] - c[t] * (i + 1 - l) * (i - l) / 2, l = i + 1;
    r -= c[t] * (d + 1 - l) * (d - l) / 2;
    return r;
}
int main() {
    auto ti = clock();
    int d;
    cin >> d;
    for(int i = 0; i < 26; i++)
        cin >> c[i];
    for(int i = 0; i < d; i++)
        for(int j = 0; j < 26; j++)
            cin >> s[i][j];
    /*vector<int> ss, tt;
    int M = -1e9;
    for(int a = 10; a < 16; a++) {
        for(int b = 0; b < 4; b++) {
            for(int z = 5; z < 16; z++) {
                int r = 0, l[33] = {};
                ss.clear();
                for(int i = 0; i < d; i++) {
                    auto m = 0.;
                    int t = 0;
                    for(int j = 0; j < 26; j++) {
                        double p = s[i][j];
                        p += c[j] * (i + 1 - l[j]) * .4 * a;
                        for(int k = 1; k < z; k++)
                            if(i + k < d)
                                p -= s[i + k][j] * (z - k) * .05 / z * b;
                        if(p > m)
                            m = p, t = j;
                    }
                    ss.push_back(t);
                    r -= c[t] * (i + 1 - l[t]) * (i - l[t]) / 2;
                    l[t] = i + 1;
                    r += s[i][t];
                }
                for(int j = 0; j < 26; j++)
                    r -= c[j] * (d + 1 - l[j]) * (d - l[j]) / 2;
                if(r > M)
                    M = r, tt.swap(ss);
            }
        }
    }*/
    random_device rd;
    mt19937 mt(rd());
    uniform_int_distribution<> rc(0, 25), r0(0, d - 1), r2(1, 6);
    vector<int> tt(d);
    for(int &i : tt)
        i = rc(mt);
    int M = 0, l[33] = {};
    for(int i = 0; i < d; i++) {
        int t = tt[i];
        M += s[i][t] - c[t] * (i + 1 - l[t]) * (i - l[t]) / 2, l[t] = i + 1;
    }
    for(int t = 0; t < 26; t++)
        M -= c[t] * (d + 1 - l[t]) * (d - l[t]) / 2;
    for(int cn = 0;
        cn < 100 || (cn = 0, (clock() - ti + 0.) / CLOCKS_PER_SEC < 1.9);
        cn++) {
        auto uu = tt;
        int x0 = r0(mt), xc = rc(mt);
        uu[x0] = xc;
        if(int y =
               sco(tt[x0], uu) + sco(xc, uu) - sco(tt[x0], tt) - sco(xc, tt);
           y > 0) {
            tt.swap(uu);
            M += y;
        }
        uu = tt;
        int x2 = r2(mt);
        uniform_int_distribution<> r1(0, d - 1 - x2);
        int x1 = r1(mt);
        x2 += x1;
        swap(uu[x1], uu[x2]);
        if(int y = sco(tt[x1], uu) + sco(tt[x2], uu) - sco(tt[x1], tt) -
                   sco(tt[x2], tt);
           y > 0) {
            tt.swap(uu);
            M += y;
        }
    }
    int S = 0;
    for(int j = 0; j < 26; j++)
        S += sco(j, tt);
    assert(S == M);
    for(int i : tt)
        cout << i + 1 << '\n';
    cerr << M << endl;
    return 0;
}


Measured memory_bytes: 3692
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <math.h>
using namespace std;    
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

double n;
double x;
long t;
long total;
    int main() {
    //nを入力
    cin >> n >> x >> t;
    long total = ceil(n/x);
    cout << total*t << endl;
}

Measured memory_bytes: 3836
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Scanner;

class Main {
    static final int MOD = 1000000007;
    static final int INF = 1 << 30;

    Main() {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        if(c%gcd(a, b)==0){
            System.out.println("YES");
        }else{            
            System.out.println("NO");
        }
    }

    static int gcd(int m, int n) {
		if (m < n)
			return gcd(n, m);
		if (n == 0)
			return m;
		return gcd(n, m % n);
	}

    public static void main(String[] args) {
        new Main();
    }
}


Measured memory_bytes: 23764
n, *a = map(int, open(0).read().split())
a = [0] + sorted(a) + [1e9+1]

l, r = 0, n+2
while r-l>1:
        mid = (l+r)//2
        m = a[mid]
        for i in range(n+1):
                if i==mid: continue
                if a[i]<=m*2: m += a[i]
                else: break
        else:
                r = mid
                continue
        l = mid
print(n-l)

Measured memory_bytes: 14284
from collections import Counter
from collections import deque
from functools import reduce
from pprint import pprint
import bisect
import copy
import fractions
import itertools
import math
import queue
import random
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers): return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers): return reduce(LCM, numbers)
def LCM(m, n): return (m * n // fractions.gcd(m, n))


w, h, x, y = MI()
halfw = w/2
halfh = h/2
ans = []

ans.append((w * h) / 2)
if x == halfw and y == halfh:
    ans.append(1)
else:
    ans.append(0)
print(*ans)


Measured memory_bytes: 67436
// Author: HarshKumar

#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
const ll N = 1e6 + 6, M = 1e9 + 7;
int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    ll a[2], b[2], m = -M * M;
    for (ll &e : a)
        cin >> e;
    for (ll &e : b)
        cin >> e;
    for (ll x : a)
        for (ll y : b)
            m = max(m, x * y);
    cout << m << '\n';
}

Measured memory_bytes: 3644
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <bitset>
using namespace std;

typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P2;
const int inf=1000000000;
int main() {
	string s,t;
	cin>>s>>t;
	int ds[100001]={};
	int dt[100001]={};
	int ls=s.length();
	int lt=t.length();
	for(int i=0;i<ls;++i){
		int k=0;
		if(s[i]=='A')k=1;
		if(s[i]=='B')k=2;
		ds[i+1]=(ds[i]+k)%3;
	}
	for(int i=0;i<lt;++i){
		int k=0;
		if(t[i]=='A')k=1;
		if(t[i]=='B')k=2;
		dt[i+1]=(dt[i]+k)%3;
	}
	int q;
	cin>>q;
	for(int i=0;i<q;++i){
		int a,b,c,d;
		cin>>a>>b>>c>>d;
		int s1=(ds[b]-ds[a-1]+3)%3;
		int t1=(dt[d]-dt[c-1]+3)%3;
		if(s1==t1){
			cout<<"YES"<<endl;
		}else{
			cout<<"NO"<<endl;
		}
	}
	return 0;
}


Measured memory_bytes: 1664
#include<iostream>
using namespace std;
int main(){
    int W,H,x,y,r;
    cin >>W >>H >>x >>y >>r;
    
    if ((x-r)>=0 && (y-r)>=0 && (x+r)<=W && (y+r)<=H){
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}


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

using namespace std;
int main()
{
    string str;
    cin>>str;
    if(str == "Sunny")  cout<<"Cloudy"<<endl;
    if(str == "Cloudy") cout<<"Rainy"<<endl;
    if(str == "Rainy") cout<<"Sunny"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
typedef long long int64;
 
signed main()
{
  int N, K;
  cin >> N >> K;
  vector< pair< int, int > > vs(N);
  for(int i = 0; i < N; i++) {
    int A, B;
    cin >> vs[i].first >> vs[i].second;
  }
  sort(begin(vs), end(vs));
 
  int64 sum = 0LL;
  for(auto &p : vs) {
    sum += p.second;
    if(sum >= K) {
      cout << p.first << endl;
      return (0);
    }
  }
 
}

Measured memory_bytes: 1792
N, C = map(int, input().split())
dic = []
for i in range(N):
  s, t, c = map(int, input().split())
  dic += [(c-1,s,t)]

L = 2*100000+1
sm = [0]*L
for c in range(C):
  tt = [0]*(L)
  for i in range(N):
    if dic[i][0]==c:
      tt[dic[i][1]*2-1] += 1
      tt[dic[i][2]*2] -= 1
  for i in range(1,L):
    tt[i] += tt[i-1]
  for i in range(L):
    if tt[i]>0:
      sm[i] += 1
print(max(sm))


Measured memory_bytes: 95804
/*  http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0505 */

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static void main (String[] args){
		try{
			Scanner s = new Scanner(System.in);
			
			
			while(true){
				int n = s.nextInt();
				int m = s.nextInt();
		
				if(n==0 && m==0) { break; }
				
				final int[] count = new int[m];
				
				for(int i=0;i<n;i++){
					for(int j=0;j<m;j++){
						int x = s.nextInt();
						if(x==1){
							count[j]++;
						}
					}
				}
				
				Integer[] indexes = new Integer[m];
				for(int i=0;i<m;i++){
					indexes[i] = i+1;
				}
				
				Arrays.sort(indexes, new Comparator<Integer>(){
					@Override
					public int compare(Integer i1, Integer i2){
						return count[i2-1] - count[i1-1];
					}
				});
				
				System.out.println(Arrays.toString(indexes).replaceAll("[,\\[\\]]",""));
			}

		}catch(Exception e){
			e.printStackTrace(System.out);
		}
	}
}

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

int main(){
    string s;
    cin >> s;
    int g_count = 0;
    for(int i = 0; i < s.size(); i++){
        g_count += (s[i] == 'p');
    }
    cout << int(s.size() / 2) - g_count << endl;
}

Measured memory_bytes: 512
<?php
class cal{

private $integer;

public function __construct($integer){
$this->integer = $integer;
}

public function check(){

	$integer = $this->integer;

	$total = $this->_check($integer, 0);
	
	return ($integer % $total) === 0;

}

private function _check($integer, $total){

	$ceil = $this->_getCeil($integer);
	
	$total = $total + $ceil;

	$quotient = $this->_getQuotient($integer);
	
	if($quotient == 0){
	return $total;
	}

	return $this->_check($quotient, $total);
}


private function _getCeil($integer){
	return $integer % 10;
}

private function _getQuotient($integer){
return floor( $integer / 10);
}

}

fscanf(STDIN, "%d", $integer);

$cal = new cal($integer);
$bool = $cal->check();

echo $bool ? 'Yes' : 'No' ;

?>

Measured memory_bytes: 4604
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <fstream>
using namespace std;
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v;}
template<class T> inline string toStr(T x) { ostringstream sout; sout << x; return sout.str();}
typedef vector<int> vi;
typedef vector<vi>  vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n) FOR(i,0,(n)-1)
const double EPS = 1e-12;
const double PI = acos(-1.0);
const int INF = INT_MAX/10;

typedef vector<vvi> vvvi;

int tdx[] = {1, 0, -1, 0};
int tdy[] = {0, 1, 0, -1};
int kdx[] = {-1, 0, 1, 0};
int kdy[] = {0, -1, 0, 1};

struct state {
	int tx, ty, kx, ky;
	state(int tx, int ty, int kx, int ky) : tx(tx), ty(ty), kx(kx), ky(ky) {};
};

int main() {
	int X, Y;
	while(cin >> X >> Y, X) {
		int tx, ty, kx, ky;
		cin >> tx >> ty >> kx >> ky;
		vvi field(Y, vi(X));
		REP(i, Y) {
			REP(j, X) {
				cin >> field[i][j];
			}
		}

		vector<vvvi> visited(Y, vvvi(X, vvi(Y, vi(X))));
		queue<state> Q;
		Q.push(state(tx-1, ty-1, kx-1, ky-1));
		int before, ans = -1;
		while(!Q.empty()) {
			state st = Q.front();
			Q.pop();

			before = visited[st.ky][st.kx][st.ty][st.tx];
			if(100 <= before) {
				continue;
			}
			if(st.kx == st.tx && st.ky == st.ty) {
				ans = before;
				break;
			}
			
			int ntx, nty, nkx, nky;
			REP(d, 4) {
				nkx = st.kx + kdx[d];
				nky = st.ky + kdy[d];
				ntx = st.tx + tdx[d];
				nty = st.ty + tdy[d];

				if(nkx<0 || X<=nkx || nky<0 || Y<=nky || field[nky][nkx]) {
					nkx = st.kx;
					nky = st.ky;
				}
				if(ntx<0 || X<=ntx || nty<0 || Y<=nty || field[nty][ntx]) {
					ntx = st.tx;
					nty = st.ty;
				}

				if(!visited[nky][nkx][nty][ntx]) {
					visited[nky][nkx][nty][ntx] = before + 1;
					Q.push(state(ntx, nty, nkx, nky));
				}
			}
		}

		if(ans == -1) {
			cout << "NA" << endl;
		} else {
			cout << ans << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 30120
def main():
  k=int(input())
  a,b = list(map(int,input().split()))
  flg=0
  for i in range(a , b+1):
    if i%k == 0 :
      flg =1
      break
  
  if flg==1:
    print("OK")
  else:
    print("NG")

main()

Measured memory_bytes: 9140
#include<stdio.h>

int memo[45] = {0};

int fib(int i){
  if(i==0){return 1;}
  if(i==1){return 1;}
  else{
    if (memo[i] != 0) return memo[i];
    memo[i] = fib(i-2) + fib(i-1);
    return memo[i];
  }
}

int main (void)
{
  int n;
  
  scanf("%d",&n);

  printf("%d\n",fib(n));
  
  return 0;
}

Measured memory_bytes: 596
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
using namespace std;
int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	bool hantei = true;
	int aa;
	cin >> aa;
	cout << 48 - aa << "\n";
}

/*
	1011
	0101

*/

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	int l,m[12],n[12],i,f;
	while(scanf("%d",&l),l)
	{
		for(i=0;i<12;++i) scanf("%d%d",&m[i],&n[i]);
		for(i=f=0;i<12;++i)
		{
			f=((l-=m[i]-n[i])<=0?i+1:0);
			if(f)break;
		}
		if(f)printf("%d\n",f);
		else puts("NA");
	}
	return 0;
}

Measured memory_bytes: 0
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n):
        a=inp()
        a-=1
        g[i].append(a)
        g[a].append(i)
    return n,g

def main():
    h, w = map(int, input().split())
    maze = [tuple(input()) for _ in range(h)]
    # h,w = inpm()
    # maze = []
    # for _ in range(h):
    #     s = tuple(input())
    #     maze.append(s)
    ans = 0
    dx = (1,0,-1,0)
    dy = (0,1,0,-1)

    for sx in range(h):
        for sy in range(w):
            if maze[sx][sy] == '#':
                continue
            else:
                d = [[-1 for _ in range(w)] for _ in range(h)]
                que = deque()
                d[sx][sy] = 0
                que.append([sx,sy])
                M = 0
                while que:
                    [qx,qy] = que.popleft()
                    for i in range(4):
                        nx=qx+dx[i]
                        ny=qy+dy[i]
                        if nx>=0 and h>nx and ny>=0 and w>ny and maze[nx][ny]=="." and d[nx][ny]==-1:
                            d[nx][ny]=d[qx][qy]+1
                            if d[qx][qy]+1>M:
                                M= d[qx][qy]+1
                            que.append([nx,ny])
                ans = max(ans,M)
    print(ans)
if __name__ == "__main__":
    main()

Measured memory_bytes: 47704
#include <bits/stdc++.h>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890123456789LL
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) ((x < 0)?-(x):x)
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge

typedef long long cat;

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define catd I64d
#endif

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(13);
	string S;
	cin >> S;
	int cnt[26] = {};
	for(int i = 0; i < (int)S.length(); i++) cnt[S[i]-'a']++;
	cat ans = 1;
	for(int i = 0; i < 26; i++) for(int j = 0; j < i; j++) ans += 1LL*cnt[i]*cnt[j];
	cout << ans << "\n";
	return 0;}

// look at my code
// my code is amazing


Measured memory_bytes: 720
#include <iostream>
using namespace std;
#define MAX 30

int main(void){
    int n,dp[MAX+1];
    dp[0] = 0; dp[1] = 1; dp[2] = 2; dp[3] = 4;
    
    for(int i = 4 ; i < MAX+1 ; i++) dp[i] = dp[i-1]+dp[i-2]+dp[i-3];
    while(1){
        cin >> n;
        if(!n) break;
        
        cout << dp[n]/10/365+1 << endl;
    }
    
    return 0;
}

Measured memory_bytes: 1160
using System;
using System.Linq;

namespace ABC126
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] s1 = Console.ReadLine().Split(' ');
            int[] n1 = s1.Select(x => int.Parse(x)).ToArray();

            string s2 = Console.ReadLine();

            string s3 = "";
            for (int i = 0; i < n1[0]; i++)
            {
                if (i == n1[1] - 1)
                {
                    s3 += char.ToLower(s2[i]);
                }
                else
                {
                    s3 += s2[i];
                }
            }

            Console.WriteLine(s3);
        }
    }
}


Measured memory_bytes: 11348
#include <iostream>
#include <algorithm>
using namespace std;
int main(void){
    int a[3];
    int k;
    std::cin >> a[0] >>a[1]>>a[2];
    std::cin >> k;
    sort(a,a+3);
    for (int i = 0; i < k; i++) {
        a[2]*=2;
    }
    std::cout << a[0]+a[1]+a[2] << std::endl;
    
}


Measured memory_bytes: 256
n,m = map(int, input().split())
red = [0]*n
ball = [1]*n
red[0] = 1
for i in range(m):
    x,y = map(int, input().split())
    if red[x-1]==1:
        red[y-1] = 1
    ball[x-1] -=1
    ball[y-1] +=1
    if ball[x-1]==0:
        red[x-1]=0
print(sum(red))



Measured memory_bytes: 51544
#include <stdio.h>
int main()
{
	int n,a,b,c,d;
	scanf("%d",&n);
	a=n/1000;
	b=n%1000/100;
	c=n%100/10;
	d=n%10;
	if((a==b&&b==c)||(b==c&&c==d))
	printf("Yes\n");
	else
	printf("No\n");
	return 0;
} 

Measured memory_bytes: 128
import java.util.Scanner;

// https://atcoder.jp/contests/abc168/tasks/abc168_c
public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ

		Scanner sc = new Scanner(System.in);
		double a = sc.nextDouble();
		double b = sc.nextDouble();
		double h = sc.nextDouble();
		double m = sc.nextDouble();
		sc.close();


		double aw = h*30.0  +  m * 0.5;
		double bw = m * 6.0;

		double w = aw - bw;
		double cos = Math.cos(Math.toRadians(w));
		if(Math.abs(cos)>Math.pow(1.0, -17)) {
			cos = 0.0;
		}

		double ans = a*a + b*b - 2.0*a*b*cos;
		System.out.println(Math.sqrt(ans));

	}
}


Measured memory_bytes: 28876
#include <bits/stdc++.h>
using namespace std;
	
int main(){
	long n,i,j,w,q,a,b,ans;
	cin >> n >> w;
	vector<long> dp1(w+1,0),dp2(w+1,0);
	for(q=0; q<n; q++){
		cin >> a >> b;
		for(i=0; i<=w-a; i++){
			dp1[i+a]=max(dp1[i+a],dp2[i]+b);
		}
		dp2=dp1;
	}
	cout << dp1[w] << endl; 
	return 0;
}

Measured memory_bytes: 1792
import statistics
N = int(input())
A = list(map(int, input().split()))

cnt = 1
for i in range(N):
    A[i] = A[i] - cnt
    cnt += 1
A.sort(reverse=True)
medA = statistics.median(A)

ans = 0
cnt = 1
for j in range(N):
    ans += abs(A[j] - medA)
    cnt += 1

print(int(ans))

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

int main(){
    long double b;
    ll a;
    cin >> a >> b;
    
    ll b_ = ll(b*100+0.01);
    
    cout << a*b_/100 << endl;
}

Measured memory_bytes: 3704
#include<iostream>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<math.h>

using namespace std;

#define INF 1000000007
#define LINF (1LL << 62)

typedef long long i64;
typedef pair<i64,i64> P;


int n, t[202], v[202];
vector<int> ma(202020,INF);
double ans = 0;

int main(){
	cin >> n;
	int T = 0;
	for(int i = 0; i < n; i++){
		cin >> t[i];
		T += t[i]*2;
	}
	int now = 0;
	for(int i = 0; i < n; i++){
		cin >> v[i];
		for(int j = 0; j <= t[i]*2; j++){
			ma[now] = min(v[i]*2, ma[now]);
			now++;
		}
		now--;
	}
	
	for(int i = 0; i <= T; i++){
		ma[i] = min(min(T-i,i), ma[i]);
	}
	for(int i = 0; i <= T; i++){
		if(i != 0){
			if(ma[i-1] < ma[i]-1){
				ma[i] = ma[i-1]+1;
			}
			if(ma[T+1-i] < ma[T-i]-1){
				ma[T-i] = ma[T+1-i]+1;
			}
		}
	}
	for(int i = 0; i <= T; i++){
		ans += ma[i];
	}
	printf("%.10f\n", ans/4);
	
	return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<vector>
#include<climits>
#include<map>
#include<string>
#include<functional>
#include<iomanip>
#include<deque>
#include<random>

using namespace std;
typedef long long ll;
typedef double lldo;
#define mp make_pair
#define pub push_back
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
ll gcd(ll a, ll b) { if (a % b == 0) { return b; } else  return gcd(b, a % b); }
ll lcm(ll a, ll b) { if (a == 0) { return b; }return a / gcd(a, b) * b; }
template<class T>ll LBI(vector<T>& ar, T in) { return lower_bound(ar.begin(), ar.end(), in) - ar.begin(); }
template<class T>ll UBI(vector<T>& ar, T in) { return upper_bound(ar.begin(), ar.end(), in) - ar.begin(); }

string S;

int main() {
	cin >> S;
	rep(i, sz(S)) {
		if (i % 2 == 0 && S[i] == 'L') {
			cout << "No" << endl;
			return 0;
		}
		if (i % 2 == 1 && S[i] == 'R') {
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	return 0;
}

Measured memory_bytes: 256
#Beginner 050 B

N = int(input())
T = list(map(int,input().split()))
M = int(input())
PX = [input() for _ in range(M)]

for _ in range(M):
    PX[_] = list(map(int, PX[_].split()))

lst = []
for i in range(M):
    lst.append(sum(T) - T[PX[i][0]-1] + PX[i][1])

for j in range(M):
    print(lst[j])

Measured memory_bytes: 3064
#include<iostream>
#define ll long long
#define rp(i,n) for(int i=0;i< n;i++)

using namespace std;



int main() {
	string s[3];
	rp(i,3) cin >> s[i];
	ll it[3];
	rp(i,3) it[i] = 0;
	ll cur = 0;
	while(true){
		if(it[cur] == s[cur].length()){
			cout << (char)('A' + cur)<<endl;
			return 0;
		}
		char nextPlayer = s[cur][it[cur]];
		it[cur]++;
		cur = (nextPlayer - 'a');
	}
	return 0;
}

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

#define rep(i,n) for(ll i = 0; i < (n); i++)
#define REP(i,n) for(ll i = 1; i < (n); i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define yesorno(a) printf(a ? "yes\n" : "no\n")
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define YESorNO(a) printf(a ? "YES\n" : "NO\n")
#define endl "\n"

using ll = long long;
using P = pair<int,int>;
using Pll = pair<ll,ll>;
using vi = vector<int>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;

const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
const int inf = (1<<30)-1;
const ll infll = (1LL<<62)-1; 


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

  int n;
  cin >> n;
  vi a(n);
  rep(i,n) cin >> a[i];
  sort(all(a));
  int ans = 0, cnt = 1;
  REP(i,n){
    if(a[i] == a[i-1]) cnt++;
    else{
      if(cnt % 2 == 1) ans++;
      cnt = 1;
    }
  }
  if(cnt % 2 == 1) ans++;
  cout << ans << endl;
}

Measured memory_bytes: 640
class Edge
  def initialize arr
    @x, @y, @cost = arr
  end
  attr_reader :x, :y, :cost
end

class Graph
  def initialize v, es
    @v, @es = v, es
    @inf = 1.0 / 0
  end

  def toAdjacencyMatrix
    return if @m
    @m = Array.new(@v).map{Array.new(@v, @inf)}
    @es.each{|e| @m[e.x][e.y] = @m[e.y][e.x] = [@m[e.y][e.x], e.cost].min}
  end

  def floydWarshall
    @dist = Marshal.load(Marshal.dump(@m))
    @v.times{|i| @dist[i][i] = 0}
    @v.times{ |i| @v.times{ |j| @v.times{ |k|
      # @dist[j][k] = [@dist[j][k], @dist[j][i] + @dist[i][k]].min
      if @dist[j][k] > x = @dist[j][i] + @dist[i][k]
        @dist[j][k] = [@dist[j][k], @dist[j][i] + @dist[i][k]].min
      end

    }}}
    return @dist
  end
end

n, m, r_ = gets.split.map(&:to_i)
r = gets.split.map{|i| i.to_i.pred}
e = m.times.map {
  a, b, c = gets.split.map(&:to_i)
  Edge.new([a.pred, b.pred, c])
}

g = Graph.new n, e
g.toAdjacencyMatrix()
d = g.floydWarshall
p r.permutation.map{|perm|
  perm.each_cons(2).map{|a,b|d[a][b]}.inject:+
}.min




Measured memory_bytes: 5684
def calc(a, n)
  s, b = [], [], []
  a.each.with_index do |e, i|
    s[i] = Array.new(i) << e
    b[i] = Array.new(i) << 0
  end
  (1 .. n - 1).each do |i|
    (0 .. n - i - 1).each do |j|
      s[j][j + i] = s[j][j + i - 1] + a[j + i];
      min = 1 / 0.0
      (0 .. i - 1).each do |k|
        bb = b[j][j + k] + b[j + k + 1][j + i]
        next if bb >= min
        x, y = s[j][j + k], s[j + k + 1][j + i]
        sum, c = 0, 0
        while (x > 0 || y > 0)
          xi, yi = x % 10, y % 10
          sum += xi * yi + c
          c = xi + yi + c < 10 ? 0 : 1
          x /= 10
          y /= 10
        end
        cost = bb + sum + c
        min = cost if cost < min
      end
      b[j][j + i] = min
    end
  end
  b[0][n - 1]
end
1.times do
  n = gets.to_i
  a = gets.split.map(&:to_i)
  puts calc(a, n)
end

Measured memory_bytes: 10676
/* 解説通り実装 */
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
  string s;
  cin>>s;
  int l = s.size();
  for(int i=0; i<l-2; i++){
    if(s[i]==s[i+1]){
      cout<<i+1<<" "<<i+2<<endl;
      return 0;
    }else if(s[i]==s[i+2]){
      cout<<i+1<<" "<<i+3<<endl;
      return 0;
    }
  }
  if(s[l-2]==s[l-1]){
    cout<<l-1<<" "<<l<<endl;
    return 0;
  }
  cout<<-1<<" "<<-1<<endl;
}

Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

long long int max(std::vector<long long int> v){
    int maxVal = 0;
    for(int i = 0; i < (long long int)v.size(); ++i) {
        if( v[i] > maxVal )
            maxVal = v[i];
    }
    return maxVal;
}
long long int min(std::vector<long long int> v){
    int minVal = 1000000;
    for(int i = 0; i < (long long int)v.size(); ++i) {
        if( v[i] < minVal )
            minVal = v[i];
    }
    return minVal;
}

int main(){
    long long int n;
    std::vector<long long int> a;
    cin >> n;
    for(long long int i=0;i<n;i++){
        long long int p;
        cin >> p;
        a.push_back(p);
    }
    cout<<max(a)-min(a)<<endl;

    return 0;
}

Measured memory_bytes: 256