akhauriyash/Code-Regression huggingface dataset:
s = input()[::-1]
size = len(s)
s += "4"

ans = 0
bef = 0

for i in range(size):
    v1 = int(s[i])
    v2 = int(s[i+1])
    if v1+bef>=6 or (v1+bef>=5 and v2>=5):
        ans += 10-(v1+bef)
        bef = 1
    else:
        ans += (v1+bef)
        bef = 0

ans += bef
print(ans)

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

const int MAXN = 1e6+6;
vector<int> P;
vector<int> C;

void decompose(long long n)
{
    int sq = sqrt(n) + 1;
    for(int i = 2; i <= sq; ++i)
    {
        if(n % i == 0)
        {
            P.push_back(i);
            int cnt = 0;

            while(n % i == 0)
            {
                ++cnt;
                n /= i;
            }

            C.push_back(cnt);
        }
    }

    if(n > 1)
    {
        P.push_back(n);
        C.push_back(1);
    }
}

long long A[MAXN];

int main()
{
    for(int i = 1; i < MAXN; ++i)
        A[i] = 1ll * i * (i + 1) / 2;



    long long n;
    cin >> n;

    decompose(n);

    int ans = 0;

    for(int i = 0; i < C.size(); ++i)
    {
        ans += upper_bound(A, A+MAXN, C[i]) - A - 1;
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 11496
#include <stdio.h>
int n;
int cnt_div(int x){
	int cnt = 2;
	for(int i=3;i<x;i+=2){
		if(x%i==0) cnt ++;
	}
	return cnt;
}
int main(){
	int cnt = 0;
	scanf("%d",&n);
	for(int i=1;i<=n;i+=2){
		if(cnt_div(i)==8){
			cnt++;
		}
	}
	printf("%d\n",cnt);
}

Measured memory_bytes: 1712
/**
   * @Author:Monk78
**/
#include<bits/stdc++.h>
using namespace std;
typedef double ll;
typedef vector<ll>Vl;
typedef pair<ll,ll>PII;
typedef vector<PII>Vll;
typedef vector<pair<ll,pair<ll,ll> > >Vlll;
typedef priority_queue<ll>PQL;
typedef map<ll,ll>MP;
#define S second;
#define F first;
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end));i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define mp make_pair
#define ms(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define mod 1000000009
#define MAX 100005
#define f(i,a,b) for(int i=(a);i<(b);i++)
#define rf(i,a,b) for(int i=(a);i>=b;i--)
#define sl(n) scanf("%lf",&n)
#define pl(n) printf("%lf",n)
#define vpshVar() int main()
vpshVar(){
    ll N,K;
    sl(N);sl(K);
    ll ans=0;
    for(ll i=1;i<=N;i++){
        ll kk=(K/i);
        int rang=ceil(log2(kk));
        ll value= ll(1/N);
        for(ll j=0;j<rang;j++){
            value=value*0.5;
        }
        //cout<<value<<endl;
        ans=ans+value;
        //ans=ans+(1/N)*
    }
    printf("%.10lf",ans);
return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, a, b) for(int i = a; i < b; i++)
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  FastIO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef long long int lli;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }

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

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    vector<vector<ll>> dp(2, vector<ll>(n));
    dp[0][0] = a[0];
    dp[1][0] = -a[0];
    for(int i = 0; i < n-1; i++){
        dp[0][i+1] = max(dp[0][i]+a[i+1], dp[1][i]-a[i+1]);
        dp[1][i+1] = max(dp[0][i]-a[i+1], dp[1][i]+a[i+1]);
    }
    cout << dp[0][n-1] << endl;
}

Measured memory_bytes: 5820
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<list>
#include<bitset>
#include<stack>
#include<memory>
#include<numeric>
using namespace std;
using namespace std::chrono;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);*/
const int mod=1000000007;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-4;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(const vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(const vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}

int main(void){
	int a,b,c;cin>>a>>b>>c;
	cout<<(a+b+c<=21?"win":"bust")<<endl;
	return 0;
}

Measured memory_bytes: 256
/*
 author : nit1n
 created : 14/09/2020 23:35:48
*/
#include<bits/stdc++.h>
#define int long long
using namespace std ;
const int N =2e5 + 5 ;

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL) ;
                                                                                
    int n ; 
    cin >> n ;
	vector<pair<int,int>> a(n) ; 
	for(int i = 0 ; i < n ; ++i)
	{
		int u , v ; 
		cin >> u >> v ; 
		a[i] = make_pair(u,v) ; 
	}
	int ans = 0;
	sort(a.begin() , a.end()) ; 
	int mn = a[0].first + a[0].second ; 
	int mx = a[0].second - a[0].first ; 
	for(int i = 1; i < n ; ++i)
	{
		ans = max(ans ,max( a[i].first + a[i].second - mn ,	a[i].first - a[i].second + mx)) ; 
		mn= min(mn, a[i].first + a[i].second) ;
		mx= max(mx , -a[i].first + a[i].second ) ;
	}
	cout << ans ;
}



Measured memory_bytes: 6296
def q2():
    n, k = [int(i) for i in input().split(" ")]
    snk = set()
    for i in range(k):
        _ = int(input())
        l = [int(i) for i in input().split(" ")]
        for j in l:
            snk.add(j)
    print(n - len(snk))

q2()

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

int main( void )
{
    int n;
    cin >> n;
    
    if ( n / 100 - n % 10 )
        cout << "No" << endl;
    else
        cout << "Yes" << endl;
}


Measured memory_bytes: 256
class DisjointSet:

    def __init__(self, N):
        self.parents = [i for i in range(N)]
        self.size = [1]*N

    def find_parent(self, x):
        path = []
        while self.parents[x] != x:
            x = self.parents[x]
            path.append(x)
        for p in path:
            self.parents[p] = x
        return x

    def find_size(self, x):
        return self.size[self.find_parent(x)]

    def union(self, x, y):
        root_x = self.find_parent(x)
        root_y = self.find_parent(y)
        if root_x != root_y:
            self.parents[root_x] = root_y
            self.size[root_y] += self.size[root_x]

def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N, M = read_ints()
    disjoint_set = DisjointSet(N)
    for _ in range(M):
        a, b = read_ints()
        disjoint_set.union(a-1, b-1)
    return max(disjoint_set.size)


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


Measured memory_bytes: 88352
#include<bits/stdc++.h>
#define LL long long
#define int long long
inline LL read(){
	char c=getchar();while (c!='-'&&(c<'0'||c>'9'))c=getchar();
	LL k=0,kk=1;if (c=='-')c=getchar(),kk=-1;
	while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();return kk*k;
}using namespace std;
void write(LL x){if (x<0)x=-x,putchar('-');if (x/10)write(x/10);putchar(x%10+'0');}
void writeln(LL x){write(x);puts("");}
int a,b,c,aa,aaa,aaaa,bb,bbb,bbbb,cc,ccc,cccc,ans;
signed main(){
	a=read();b=read();c=read();ans=1e9;
	for (int i=-100;i<=100;i++){
		aa=max((i-a+1)/2,0ll);aaa=a+aa*2;aaaa=aaa-i;
		bb=max((i-b+1)/2,0ll);bbb=b+bb*2;bbbb=bbb-i;
		cc=max((i-c+1)/2,0ll);ccc=c+cc*2;cccc=ccc-i;
		ans=min(ans,aa+aaaa+bb+bbbb+cc+cccc);
	}writeln(ans);
}


Measured memory_bytes: 256
import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		int[] v = new int[500000];
        for(int i = 0;i < 500000;i++){
            v[i] = 1;
        }
        int p = 3;
        while(true){
            if(p*p > 1000000){
                break;
            }else{
                if(v[(p-1)/2] == 0){
                    p += 2;
                }else{
                    int t = p*p;
                    while(t < 1000000){
                        v[(t-1)/2] = 0;
                        t += 2*p;
                    }
                    p += 2;
                }
            }
        }
        v[0] = 0;
		while(scan.hasNext()){
			int n = scan.nextInt();
			if(n == 0){
				break;
			}
			int count = 0;
			for(int i = 1;i < n/2;i++){
				if(v[i] != 1){
					continue;
				}
				if(v[(n-2*i-2)/2] == 1){
					count += ((n-2*i-2)/2 == i)?2:1;
				}
			}
			System.out.println(count/2);
        }
	}
}

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

using namespace std;

string num;
int k, len;
char least = '0';
bool disliked[10];

inline void setGreaterUtil(int pos)
{
    for (int i = pos; i < len; i++)
        num[i] = least;
}

void setGreater(int pos)
{
        if (num[pos] == '9')
        {
            if (disliked[0])
                setGreaterUtil(pos);
                setGreater(pos-1);
        } else {
            num[pos]++;
            if (disliked[num[pos]-'0'])
                setGreater(pos);
            else
                setGreaterUtil(pos+1);
        }
}

int main()
{
//    while (true)
//    {
        cin >> k;

        num = to_string(k);
        len = static_cast<int>(num.length())+1;

        cin >> k;

        for (int i = 0; i < k; i++) {
            int temp;
            cin >> temp;
            disliked[temp] = true;
        }

        for (int i = 0; i < 10; i++)
            if (!disliked[i]) {
                least = static_cast<char>('0' + i);
                break;
            }

        num = '0' + num;

        for (auto i = (len - 1); i >= 1; i--)
        {
            if (disliked[num[i] - '0'])
                setGreater(i);
        }

        if (num[0] == '0')
            num = num.substr(1, len-1);

        cout << num;
//    }


}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define PI          acos(-1)
#define INF         100000000
#define sc(n)       scanf("%d",&n);
#define ssc(n)      scanf("%s",n);
#define lsc(n)      scanf("%lld",&n);
#define dsc(n)      scanf("%lf",&n);
#define csc(n)       scanf("%c",&n);
#define LL          long long int
#define UI          unsigned int
#define ULL         unsigned long long int
#define DB          double
#define pii         pair<int,int>
#define VI          vector<int>
#define MII         map<int,int>
#define PB          push_back
#define MP          make_pair
#define M(mx,a)     mx=max(mx,a)
#define IT          ::iterator
#define all(a)      a.begin(),a.end()
#define mems(a,b)   memset(a,b,sizeof(a))
#define F(i,a,b)    for(i=a;i<b;i++)
#define IN(n,aa)    for(i=0;i<n;i++)scanf("%d",&aa[i]);
#define PNT(n,aa)   for(i=0;i<n;i++)printf("%lld ",aa[i]);
#define mod         1000000007
#define NUM         100009
#define NUM2        1000000000


int aa[NUM][65];
LL dd[NUM][65];

void ffff()
{
    int i,j;
    LL a=1;
    for(i=1;i<NUM;i++)
    {
        for(j=0;j<10;j++)aa[i][j]=a*j%13;
        a=a*10%13;
    }
}

int main()
{
    int T=1,QQ=0;
    //cin >> T ;
    while(T--)
    {
        int n,i,j,k;
        string ss;
        cin >> ss;
        reverse(all(ss));
        ffff();
        mems(dd,0);
        dd[0][0]=1;
        n=ss.size();
        for(i=0;i<n;i++)
        {
            if(isdigit(ss[i]))
            {
                for(j=0;j<13;j++)
                {
                    dd[i+1][(aa[i+1][ss[i]-'0']+j)%13]=dd[i][j];
                }
            }
            else
            {
                for(j=0;j<10;j++)
                {
                    for(k=0;k<13;k++)
                    {
                        LL ii=(aa[i+1][j]+k)%13;
                        dd[i+1][ii]=(dd[i+1][ii]+dd[i][k])%mod;
                    }
                }
            }
        }
        cout << dd[n][5] << endl;
    }
}

//printf("Case %d: ",++QQ);


Measured memory_bytes: 79844
#include <iostream>
#include <vector>
#include<list>
#include <algorithm>
#include <string>
#include <math.h>
#include<map>
#include <utility>

#include<queue>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
 
#define INF (1e10)
typedef long long unsigned int ll;
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
 

template<typename T>
int vector_finder(std::vector<T> vec, T number) {
  auto itr = std::find(vec.begin(), vec.end(), number);
  size_t index = std::distance( vec.begin(), itr );
  if (index != vec.size()) { // 発見できたとき
    return 1;
  }
  else { // 発見できなかったとき
    return 0;
  }
}

template<typename T>
T gcd(T a,T b){
	if(b>0){
		return gcd(b, a % b);
	}else{
		return a;
	}
}

template<typename T>
T lcm(T a,T b){
	T g = gcd(a, b);
	return a * b / g;
}

void clear( std::queue<pair<int,int> > &q )
{
   std::queue<pair<int,int> > empty;
   std::swap( q, empty );
}

int N,M;
int ans = 0;

int main()
{
	cin >> N;
	ll a[N];
	vector<int> b;
	REP(i, N)
	{
		cin >> a[i];
	}

	if(N%2==1){
		for (int i = N - 1; i >= 0;i-=2){
			b.push_back(a[i]);
		}
		for (int i = 1; i <= N - 2;i+=2){
			b.push_back(a[i]);
		}
	}else{
		for (int i = N - 1; i >= 1;i-=2){
			b.push_back(a[i]);
		}
		for (int i = 0; i <= N - 2;i+=2){
			b.push_back(a[i]);
		}
	}


	REP(i,N){
		cout << b[i] << " ";
	}

	return 0;
}

Measured memory_bytes: 4596
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll MOD = 1000000007;

#define vec                vector<int>
#define vecll              vector<ll>
#define vecd               vector<double>
#define vecst              vector<string>
#define vecb               vector<bool>
#define vec2(var, n, m)    vector<vector<int>>  var(n, vector<int>(m, 0))
#define vecb2(var, n, m)   vector<vector<bool>> var(n, vector<bool>(m, false))
#define vecll2(var, n, m)  vector<vector<ll>>   var(n, vector<ll>(m, 0))

#define rep(i,n)         for(ll i=(ll)0; i<(ll)n; i++)
#define REP(i,m,n)       for(ll i=(ll)m; i<(ll)n; i++)
#define arr(var, n)      vec var(n); rep(i,n){cin >> var[i];}
#define arrll(var, n)    vecll var(n); rep(i,n){cin >> var[i];}
#define arrst(var, n)    vecst var(n); rep(i,n){cin >> var[i];}
#define all(var)         (var).begin(), (var).end()
#define sortall(var)     sort(all(var))
#define uniqueall(v)     v.erase(unique(v.begin(), v.end()), v.end());
#define f_sum(var)       accumulate(all(var), 0)
#define f_sumll(var)     accumulate(all(var), 0LL)
#define chmin(v1, v2)    v1 = min(v1, v2)
#define chmax(v1, v2)    v1 = max(v1, v2)
#define pb(var)          push_back(var)
#define prt(var)         cout << (var) << "\n"
#define prtd(n, var)     cout << fixed << setprecision(n) << (var) << "\n"
#define prtfill(n, var)  cout << setw(n) << setfill('0') << (var);
#define prt2(v1, v2)     cout << (v1) << " " << (v2) << "\n"
#define prt3(v1, v2, v3) cout << (v1) << " " << (v2) << " " << (v3) << "\n"
#define prtall(v)        rep(i,v.size()){cout<<v[i]<<(i!=v.size()-1?" ":"\n");}
void prtok(bool ok){prt(ok ? "Yes" : "No");}
//----------------------------------------------------------------

int main(void) {
  ll x, a, b;
  cin >> x >> a >> b;
  if(b<=a){
    prt("delicious");
  } else if(b>a&& b<=a+x){
    prt("safe");
  } else {
    prt("dangerous");
  }
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define LLINF 9223372036854775807
#define MOD ll(1e9+7)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cerr<<#x<<": "<<x<<endl

int main(){
    ll n, t;
    cin >> n >> t;

    vector<ll> a(n), b(n);
    for(int i = 0; i < n; i++){
        cin >> a[i] >> b[i];
    }

    ll MAXSIZE = t;
    vector<vector<ll>> dp(n+1, vector<ll>(MAXSIZE, 0));
    vector<vector<ll>> dprev(n+1, vector<ll>(MAXSIZE, 0));


    for(int i = 0; i < n; i++){
        for(int j = 0; j < MAXSIZE; j++){
            if(j-a[i]>=0){
                dp[i+1][j] = max(dp[i][j-a[i]]+b[i], dp[i][j]);
            }else{
                dp[i+1][j] = dp[i][j];
            }
        }
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < MAXSIZE; j++){
            if(j-a[n-1-i]>=0){
                dprev[i+1][j] = max(dprev[i][j-a[n-1-i]]+b[n-1-i], dprev[i][j]);
            }else{
                dprev[i+1][j] = dprev[i][j];
            }
        }
    }

    ll ans = 0;
    for(int i = 0; i < n; i++){
        ll tmpmax = 0;
        for(int j = 0; j < t; j++){
            ll tmp = 0;
            if(i>=0){tmp += dp[i][j];}
            if(n-1-i>=0){tmp += dprev[n-1-i][t-1-j];}
            tmpmax = max(tmpmax, tmp);
        }
        ans = max(ans, tmpmax + b[i]);
    }
    cout << ans << endl;
    return 0;

}


Measured memory_bytes: 141184
#include <bits/stdc++.h>
using namespace std;
using vec = vector<int>;
using intk = int64_t;

int main() {
int N;
  cin >>N;
  vector<pair<int,int>> A(N);
  for(int i=0;i<N;i++){
    int a;
    cin >> a;
    A[i] = make_pair(a,i+1);
  }
  sort(A.begin(),A.end());
  for(int i=0;i<N;i++){
   cout << A[i].second;
    if(i != N-1) cout <<" ";
    else cout <<endl;
  }
}
  


Measured memory_bytes: 1664
import sys
from bisect import bisect_left as bi_l, bisect_right as bi_r

n = int(sys.stdin.readline().rstrip())
a = sorted(map(int, sys.stdin.readline().split()))
b = sorted(map(int, sys.stdin.readline().split()))
c = sorted(map(int, sys.stdin.readline().split()))

def main():
    combs = 0
    for x in b:
        combs += bi_l(a, x) * (n - bi_r(c, x))
    print(combs)

if __name__ ==  '__main__':
    main()

Measured memory_bytes: 22720
# -*- coding: utf-8 -*-
from sys import stdin

n = int(stdin.readline().rstrip())
l_2 = 2
l_1 = 1
l_0 = 0

if n == 0:
    l_0 = l_2
elif n == 1:
    l_0 = l_1
else:
    for i in range(2,n+1):
        l_0 = l_2 + l_1
        l_2 = l_1
        l_1 = l_0
print(l_0)

Measured memory_bytes: 3060
import javax.swing.plaf.basic.BasicInternalFrameTitlePane;
import  java.io.*;
import  java.math.*;
import java.nio.Buffer;
import java.sql.SQLSyntaxErrorException;
import  java.util.*;
import  java.text.*;
import java.util.regex.Pattern;
import java.util.stream.Collectors;


public class Main {


    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        long k=cin.nextLong();
        int n=cin.nextInt();
        long num[]=new long[n+1];
        long num1[]=new long[n+1];
        num[1]=cin.nextLong();
        for(int i=2;i<=n;i++){
            num[i]=cin.nextLong();
            num1[i-1]=num[i]-num[i-1];
        }

        long sum=0;
        num1[n]=k+num[1]-num[n];
        long ans=0;
        for(int i=1;i<=n;i++){
            ans=Math.max(ans,num1[i]);
            sum+=num1[i];
        }
        sum=sum-ans;
        System.out.println(sum);
    }
}


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

typedef long long ll;

int main(void){
  ll h,w,result=0;
  scanf("%lld",&h);
  scanf("%lld",&w);
  result = (h*w+1)/2;
  if(h==1||w==1){
    result = 1;
  }
  printf("%lld",result);
  
  return 0;
}
  
  

Measured memory_bytes: 128
<?php
$input = STDIN;

list($r, $c) = explode(' ', trim(fgets($input)));

$s = array_fill(0, $c, 0);

for ($i = 0; $i < $r; $i++) {
    $line = trim(fgets($input));
    
    print $line;

    $line = explode(' ', $line);
    print ' ' . array_sum($line) . "\n";
    
    foreach ($line as $key => $value) {
        $s[$key] += $value;
    }
}

print implode(' ', $s) . ' ' . array_sum($s) . "\n";

?>


Measured memory_bytes: 9316
#include <stdio.h>

int main(void)
{
	int a, b, c;
	int h, m, s;
	int zan, sanbai;
	int sanh, sanm, sans;
	
	while (1) {
		scanf("%d %d %d", &h, &m, &s);
		if ((h + m + s) == -3) {
			break;
		}
		
		zan = 7200 - (h * 3600 + m * 60 + s);
		
		sanbai = zan * 3;
		if (zan / 3600 != 0) {
			h = zan / 3600;
			zan = zan % 3600;
		}
		else {
			h = 0;
		}
		if (zan / 60 != 0) {
			m = zan / 60;
			s = zan % 60;
		}
		else {
			m = 0;
			s = zan % 60;
		}
		if (sanbai / 3600 != 0) {
			sanh = sanbai / 3600;
			sanbai = sanbai % 3600;
		}
		else {
			sanh = 0;
		}
		if (sanbai / 60 != 0) {
			sanm = sanbai / 60;
			sans = sanbai % 60;
		}
		else {
			sanm = 0;
			sans = sanbai % 60;
		}
		
		printf("%02d:%02d:%02d\n", h, m, s);
		printf("%02d:%02d:%02d\n", sanh, sanm, sans);
	}
	
	return (0);
}	
	
	

Measured memory_bytes: 612
#include <cstdio>
#include <vector>
using namespace std;

int main()
{
    int N, X;
    scanf("%d%d", &N, &X);
    vector<int> L(N);
    for (int i = 0; i < N; ++i)
    {
        scanf("%d", &L[i]);
    }
    int ans = 1;
    int d = 0;
    for (int i = 0; i < N; ++i)
    {
        d = d + L[i];
        if (d <= X) ++ans;
    }
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 256
//#include <fsociety>
#include <cmath>
#include <deque>
#include <algorithm>
#include <iterator>
#include <list>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <unordered_set>
#include <stack>
#include <string>
#include <vector>
#include <iostream>
//end of libraries ;
#define INF 99999999999
#define N 300003
#define F first
#define S second
#define pb push_back
#define ll long long
#define fcin ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
int n  , x  , c;
int gcd(int x , int y){
	if(x>y) swap(x,y);
	if(x==0) return y;
	else return gcd(y%x,x);
}
vector <int> dif;
int main(){
fcin;

	cin>>n>>x;
	vector<int>a(n);
	for(int i = 0 ; i < n ; i++) cin>>a[i];
	a.pb(x);
	sort(a.begin(),a.end());
	for(int i = 1 ; i < a.size() ; i++){
		dif.pb(a[i]-a[i-1]);
	}
	sort(dif.begin(),dif.end());
	c = gcd(dif[0],dif[1]);
	for(int i = 2 ; i < dif.size() ; i++){
		c = gcd(c,dif[i]);
	}
	
	cout<<c<<endl;

}

Measured memory_bytes: 1528
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repr(i,n) for(int i = (int)(n); i >= 0; i--)
#define all(v) v.begin(),v.end()
typedef long long ll;

int main(){
    ll N;
    cin >> N;
    vector<ll> A(N);
    rep(i,N){
        cin >> A[i];
    }
    bool plus = true;
    bool minus = true;
    ll ans = 1;
    rep(i,N - 1){
        if (A[i + 1] > A[i]){
            if (!plus){
                plus = true;
                minus = true;
                ans++;
            }
            else{
                minus = false;
            }
        }
        else if (A[i + 1] < A[i]){
            if (!minus){
                plus = true;
                minus = true;
                ans++;
            }
            else{
                plus = false;
            }
        }
    }
    cout << ans << endl;
}


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

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

typedef long long ll;
using namespace std;
int mod = 1000000007;

struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }
    
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};

int main(void){
    ll N, M; cin >> N >> M;
    UnionFind uf(N);
    vector<ll> ans(M, 0);
    ans[M-1] = (N-1)*N/2; //最後の橋が崩落した時の不便さは最大でnC2
    pair<int, int> bridge[M];
    rep(i, M) cin >> bridge[i].first >> bridge[i].second;
    for(int i = M-1; i >= 1; i--){
        //bridge[i]を建設すると,uf.size(from)*uf.size(to)だけ不便さが減る
        //ただしこれは!uf.issame(from, to)の時のみ
        int a = bridge[i].first-1, b = bridge[i].second-1;
        if(!uf.issame(a, b)){
            ans[i-1] = ans[i] - uf.size(a)*uf.size(b);
            uf.merge(a, b);
        }
        else ans[i-1] = ans[i];
    }
    rep(i, M) cout << ans[i] << endl;
    return 0;
}

Measured memory_bytes: 3328
#include<stdio.h>
int main()
{
    unsigned long long  n,a,b,temp,i;
    scanf("%llu",&n);
    a=2;
    b=1;
    for(i=2;i<=n;i++)
        {
            temp=a+b;
            a=b;
            b=temp;
        }
        printf("%llu",b);
                return 0;
}




Measured memory_bytes: 1700
x, k, d = map(int, input().split())
ini = abs(x) // d
if k <= ini:
    print(abs(abs(x)-k*d))
    exit()
if (k-ini)%2 == 0:
    print(abs(abs(x)-ini*d))
else:
    print(abs(abs(x)-ini*d-d))

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

string s;

int main() {
    cin >> s;
    int n = s.length();
    for(int i = 0; i + 2 < n; i++) {
        if(s[i] == s[i+1] || s[i] == s[i+2]) return cout << i + 1 << " " << i + 3 << endl, 0;
    }
    if(n >= 2 && (s[n-1] == s[n-2])) return cout << n - 1 << " " << n << endl, 0;

    cout << "-1 -1" << endl;
}

Measured memory_bytes: 512
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
using namespace std;
using Graph = vector<vector<int>>;
typedef long long ll;
const int mod= 1e+9+7;

int main(){
    ll N,K; cin>>N>>K;
    ll ans =0;
    for(ll i=K;i<=N;i++){
        ans+=i*(N+N-i+1)/2-i*(0+i-1)/2+1;
        ans%=mod;
    }
    cout<<ans+1<<endl;
}




Measured memory_bytes: 3632
n, m = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
diff = [0] * (m-1)
for i in range(m-1):
    diff[i] = x[i+1] - x[i]
diff.sort(reverse = True)
print(sum(diff[(n-1):]))


Measured memory_bytes: 13968
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<climits>
#include<map>
#include<set>
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define INF 1<<30
#define F first
#define S second
using namespace std;
typedef pair<int,int> P;
int h,w;
int cmap[110][110];
bool visited[110][110];
static const int dx[4] = {0,1,0,-1};
static const int dy[4] = {1,0,-1,0};

void dfs(char c,int x,int y){
  visited[y][x] = true;
  for(int i=0;i<4;i++){
    int nx = x+dx[i],ny = y+dy[i];
    if(0<=nx && nx<w && 0<=ny && ny <h && c == cmap[ny][nx] && !visited[ny][nx]){
      dfs(c,nx,ny);
    }
  }

}



int main(){
  while(true){
    int cnt=0;
    cin >> h >> w;
    if(h+w  == 0)break;
    string s;
    for(int i=0;i<h;i++){
      cin >> s;
      for(int j=0;j<s.length();j++){
	cmap[i][j] = s[j];
	visited[i][j] = false;
      }
    }

    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
	if(!visited[i][j]){
	  cnt++;
	  dfs(cmap[i][j],j,i);
	}	
      }
    }
    cout << cnt << endl;
  }
return 0;
}

Measured memory_bytes: 1732
<?php
$n = trim(fgets(STDIN));
$arr = explode(' ', trim(fgets(STDIN)));
$a = $arr[0];
$b = $arr[1];

$c = floor($a / $n);

$d = $n * ($c + 1);

if (($a % $n) == 0){
    echo 'OK';
    return;
}

if (($b % $n) == 0){
    echo 'OK';
    return;
}

if ($a <= $d && $b >= $d){
    echo 'OK';
    return;
}

if ((($b - $a) + 1) >= $n) {
    echo 'OK';
    return;
}

echo 'NG';
    return;

?>


Measured memory_bytes: 16168
class Factorials:
    # nに十分大きい数を入力
    def __init__(self, n, mod):
        self.mod = mod

        # self.fac[i] ≡ i! (factorial:階乗)
        self.fac = [1]
        num = 1
        for i in range(1, n+1):
            num *= i
            num %= mod
            self.fac.append(num)

        # self.rec[i] ≡ 1 / i! (reciprocal:逆数)
        num = pow(num, mod-2, mod)
        self.rec = [1 for i in range(n+1)]
        self.rec[n] = num
        for i in range(n-1, 0, -1):
            num *= i + 1
            num %= mod
            self.rec[i] = num

    # comb(n, r) ≡ nCr
    def comb(self, n, r):
        return self.fac[n] * self.rec[r] * self.rec[n - r] % self.mod
    
    # perm(n, r) ≡ nPr
    def perm(self, n, r):
        return self.fac[n] * self.rec[n-r] % self.mod

    # fact(n) ≡ n!
    def fact(self, n):
        return self.fac[n]

n, m = map(int, input().split())
mod = 10 ** 9 + 7

if abs(n - m) > 1:
    print(0)
    exit()

fct = Factorials(n + 1, mod)

if abs(n - m) == 1:
    print(fct.fact(n) * fct.fact(m) % mod)

else:
    print(2 * fct.fact(n) * fct.fact(m) % mod)

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

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
typedef vector<int> vi;
#define rep(i, n) for(int i = 0; i < n; ++i)
#define rInt(a) scanf("%d",&a);

main(){
   ll x, y;
   cin >> x >> y;
   int ans =0;
   for(ll i=x;i<=y;i*=2) ans++;
   cout << ans << endl;
}

Measured memory_bytes: 256
open Printf open Scanf
open Array

let () = scanf " %d %d" @@ fun a b ->
  if a=b then print_int a
  else if b=a+1 then print_int @@ a lxor b
  else
    let l = if a mod 2 = 0 then a else a+1 in
    let r = if b mod 2 = 1 then b else b-1 in
    print_int @@
      let pairs = (r-l+1) / 2 in
      let w = if pairs mod 2 = 0 then 0 else 1
      in
      w lxor (if l=a+1 then a else 0) lxor (if r=b-1 then b else 0)

Measured memory_bytes: 384
S = input()
flag = True
odd = "RUD"
even = "LUD"

for i in range(len(S)):
  if i % 2 == 0 and odd.count(S[i]) == 0:
    flag = False
    break
  elif i % 2 != 0 and even.count(S[i]) == 0:
    flag = False
    break

if flag:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 3060
import java.util.Scanner;
class Main
{
    public static void main(String args[])
    {
	int m,f,r;
	Scanner scan=new Scanner(System.in);
	while(true)
	    {
		m=scan.nextInt();
		f=scan.nextInt();
		r=scan.nextInt();
		if((m==-1) && (f==-1) && (r==-1))
		    
			
			break;
		    
		else if((m==-1) || (f==-1))System.out.println("F");
		else if(m+f>=80)System.out.println("A");
		else if((m+f>=65) && (m+f<80))System.out.println("B");
		else if(((m+f>=50) && (m+f<65)) || (r>=50))System.out.println("C");
		else if((m+f>=30) && (m+f<50))System.out.println("D");
		else if(m+f<30)System.out.println("F");
	    }
    }
}

Measured memory_bytes: 19200
#include<bits/stdc++.h>
using namespace std;
#define ll long long

int main()
{
	ll n;
	cin>>n;
	ll x=n;
	for(ll i=0;i<=n;i++)
	{
		x=i;
		if(i*i>n)
			break;
	}
	ll min=n;
	for(ll i=1;i<=x;i++)
	{
		if(n%i==0)
		{
			ll j=n/i;
			ll cnt=i+j-2;
			if(min>cnt)
				min=cnt;
		}
	}
	cout<<min<<endl;

	return 0;
}

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,K=MI()
    ab=[[0,0] for _ in range(N)]
    for i in range(N):
        ab[i][0],ab[i][1]=MI()
        
    ab.sort()
    
    ans=0
    temp=0
    for i in range(N):
        temp+=ab[i][1]
        if  temp>=K:
            ans=ab[i][0]
            break
        
    print(ans)
        

main()


Measured memory_bytes: 54128
import java.util.*;

public class Main {

	public static long calc(long cnt) {
		if (cnt <= 1)
			return 0;
		long ans = 0;
		if (cnt % 2 == 0) {
			ans = cnt / 2;
			ans *= (cnt - 1);
		} else {
			ans = (cnt - 1) / 2;
			ans *= cnt;
		}
		return ans;
	}

	public static String mysort(String s) {
		char c[] = s.toCharArray();
		Arrays.sort(c);
		String ans = new String(c);
		return ans;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long cnt = 0, ans = 0;
		String s[] = new String[n];
		for (int i = 0; i < n; ++i) {
			s[i] = sc.next();
			String tm = mysort(s[i]);
			s[i] = tm;
		}
		sc.close();
		Arrays.sort(s);
		String t = s[0];
		for (int i = 0; i < n; ++i) {
			if (t.equals(s[i]))
				++cnt;
			else {
				t = s[i];
				ans += calc(cnt);
				cnt = 1;
			}
		}
		ans += calc(cnt);
		System.out.println(ans);
	}
}


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

typedef long long ll;

int main(){
    ll N;
    cin >> N;
    vector<ll> v(N);
    for(int i = 0; i < N; i++){
        cin >> v.at(i);
    }

    ll res = 0;
    ll right = 0;     
    ll sum = 0;
    for (ll left = 0; left < N; ++left) {
        while (right < N && (sum + v[right] == (ll)(sum^v[right]))){
            /* 実際に right を 1 進める */
            sum+= v[right];
            ++right;
        }
        /* break した状態で right は条件を満たす最大なので、何かする */
        // ex: res += (right - left);
        res += right - left;

        /* left をインクリメントする準備 */
        // ex: if (right == left) ++right;
        // ex: else sum -= a[left];
        if(right == left){
            ++right;
        } else { 
            sum -= v[left];
        }
    }
    cout << res << endl;

}

Measured memory_bytes: 1792
# -*- coding: utf-8 -*-

N,x = map(int, input().split())
a = list(map(int, input().split()))

a_sorted = sorted(a)

num = 0
reminder = x
for i in range(N):
    reminder -= a_sorted[i]
    if reminder>=0:
       num += 1
    else:
        break

if reminder>0:
    num -= 1
    
print(num)


Measured memory_bytes: 9088
#include <stdio.h>


int main(){
	
	int a,i,n[101],sum=0,b,p[101],x[101];
	
	scanf("%d",&a);
	
	for(i=0;i<a;i++){
		scanf("%d",&n[i]);
		sum=sum+n[i];
	}
	
	scanf("%d",&b);
	
	for(i=0;i<b;i++){
		scanf("%d %d",&p[i],&x[i]);
	}
	
	for(i=0;i<b;i++){
		printf("%d\n",sum-(n[p[i]-1]-x[i]));
	}
	
	return 0;
}


Measured memory_bytes: 128
from collections import deque
def main():
    h,w,k = map(int,input().split())
    x,y,gx,gy = map(int,input().split())
    x -= 1
    gx -= 1
    y -= 1
    gy -= 1
    c = [list(input()) for _ in range(h)]
    d = [[-1 for _ in range(w)] for _ in range(h)]
    dx = (1, 0, -1, 0)
    dy = (0, 1, 0, -1)
    que = deque()
    que.append((x,y))
    d[x][y] = 0
    while que:
        (qx,qy) = que.popleft()
        if qx == gx and qy == gy:
            break
        for i in range(4):
            for K in range(1,k+1):
                nx = qx + dx[i]*K
                ny = qy + dy[i]*K
                if not(nx>=0 and h>nx and ny>=0 and w>ny) or c[nx][ny] == '@' or (d[nx][ny] != -1 and d[nx][ny] < d[qx][qy]+1):
                    break
                if d[nx][ny] == -1 or d[nx][ny] > d[qx][qy]+1:
                    d[nx][ny] = d[qx][qy] + 1
                    que.append((nx,ny))
    print(d[gx][gy])
 
 
if __name__ == "__main__":
    main()

Measured memory_bytes: 176444
def main():
    q, h, s, d = map(int, input().split())
    n = int(input()) * 100
    h = min(h, 2*q)
    s = min(s, 2*h)
    d = min(d, 2*s)
    ans = 0
    vals = [(200, d), (100, s), (50, h), (25, q)]
    for m, val in vals:
        c = n // m
        n -= m * c
        ans += val*c
    print(int(ans))


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include<iostream>
#include<set>
#include<map>
#include<unordered_set>
#include<cmath>
#include<algorithm>
using namespace std;
#include<vector>
#define int long long int
#define mod 1000000007
int32_t main()
{
	int n,k;
	cin>>n>>k;
	int prefix[n+1][k+1];
	int value[n+1][k+1];
	int i,j;
	i=n;
	for(j=0;j<=k;j++)
	{
		prefix[n][j]=1;
	}
	for(i=0;i<=n;i++)
	{
		for(j=0;j<=k;j++)
		{
			value[i][j]=0;
		}
	}
	int arr[n];
	for(i=0;i<n;i++)
	   cin>>arr[i];
	for(j=n-1;j>=0;j--)
	{
		for(i=0;i<=k;i++)
		{
			int val=arr[j];
			int start=i-val;
			int end=i;
			start=max(0LL,start);
			int here=prefix[j+1][end];
			if(start>=1)
			{
				here-=prefix[j+1][start-1];
			}
			here=here%mod;
			if(here<0)
			   here+=mod;
			value[j][i]=here;
		}
		prefix[j][0]=value[j][0];
		for(i=1;i<=k;i++)
		{
			prefix[j][i]=value[j][i]+prefix[j][i-1];
			prefix[j][i]%=mod;
		}
	}
	int answer=value[0][k];
	answer%=mod;
	if(answer<0)
	   answer+=mod;
	cout<<answer<<endl;
}



Measured memory_bytes: 161220
N, K = list(map(int, input().split()))
h = list(map(int, input().split()))

INF = float('inf')
dp = [0]

for i in range(1, N):
    min_t = INF
    for j in range(1, K+1):
        if i - j < 0:
            continue
        min_t = min(min_t, dp[i-j] + abs(h[i-j] - h[i]))
    dp.append(min_t)

print(dp[N-1])


Measured memory_bytes: 57952
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
constexpr int MOD = 1000000007;
constexpr int INF = numeric_limits<int>::max() / 2;
typedef pair<int,int> P;
using Graph = vector<vector<int>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long double PI = acos(-1.0);
// cout << fixed << setprecision(14);
 
signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;
	N %= 1000;
	if(N == 0) cout << 0 << endl;
	else cout << 1000-N << endl;
}

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

bool in(int x, int y) {
	return 0 <= x && x <= 5000 && 0 <= y && y <= 5000;
}

int main()
{
	cin.sync_with_stdio(false);
	int n;
	while (cin >> n, n) {
		vector<vector<bool>> ex(5001, vector<bool>(5001));
		vector<int> x(n), y(n);
		for (int i = 0; i < n; i++) {
			cin >> x[i] >> y[i];
			ex[x[i]][y[i]] = true;
		}
		int res = 0;
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				int dx = x[j] - x[i], dy = y[j] - y[i];
				swap(dx, dy); dx *= -1;
				if (in(x[i] + dx, y[i] + dy) && in(x[j] + dx, y[j] + dy) && ex[x[i] + dx][y[i] + dy] && ex[x[j] + dx][y[j] + dy]) {
					res = max(res, dx * dx + dy * dy);
				}
				dx *= -1; dy *= -1;
				if (in(x[i] + dx, y[i] + dy) && in(x[j] + dx, y[j] + dy) && ex[x[i] + dx][y[i] + dy] && ex[x[j] + dx][y[j] + dy]) {
					res = max(res, dx * dx + dy * dy);
				}
			}
		}
		cout << res << endl;
	}
	return 0;
}



Measured memory_bytes: 6296
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>

using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> P;
typedef vector<P> vpl;
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int inf = 1<<30;
const ll linf = 1LL<<62;
const int mod = 1e9 + 7;
const int MAX = 510000;
const int V = 100005;
ll dy[8] = {1,0,-1,0,1,-1,1,-1};
ll dx[8] = {0,1,0,-1,1,-1,-1,1};

bool isPrime(ll x){
    if(x==1) return false;
    for(ll i=2; i<=sqrt(x); i++){
        if(x % i == 0) return false;
    }
    return true;
}

int main() {
    vl primeSum(V,0);
    REP(i,1,V){
        ll c = (isPrime(i) && isPrime((i+1)/2)) ? 1 : 0;
        primeSum[i+1] = primeSum[i] + c;
    }
    ll q; cin >> q;
    while(q--){
        ll l,r; cin >> l >> r;
        cout << primeSum[r+1] - primeSum[l] << endl;
    }
}


Measured memory_bytes: 1408
#include <iostream>
#include <cctype>

using namespace std;

int main(){
 	char moji;
	while(true){
            cin.get(moji);
            if (moji == '\n') break;
	    if (islower(moji)) cout << (char)toupper(moji);
            else if (isupper(moji)) cout << (char)tolower(moji);
	    else cout << moji;
}
 cout << endl;
    return 0;
}

Measured memory_bytes: 1124
M, D = map(int, input().split())
ans = 0

for m in range(1, M + 1):
    for d in range(1, D + 1):
        d1 = d // 10
        d2 = d % 10
        if d1 >= 2 and d2 >= 2 and m == d1 * d2:
            ans += 1
print(ans)

Measured memory_bytes: 38896
#include<algorithm>
#include<algorithm>     //sort,二分探索,など
#include<bitset>        //固定長bit集合
#include<cmath>         //pow,logなど
#include<complex>       //複素数
#include<deque>         //両端アクセスのキュー
#include<functional>    //sortのgreater
#include<iomanip>       //setprecision(浮動小数点の出力の誤差)
#include<iostream>      //入出力
#include<iterator>      //集合演算(積集合,和集合,差集合など)
#include<map>           //map(辞書)
#include<numeric>       //iota(整数列の生成),gcdとlcm(c++17)
#include<queue>         //キュー
#include<set>           //集合
#include<stack>         //スタック
#include<string>        //文字列
#include<unordered_map> //イテレータあるけど順序保持しないmap
#include<unordered_set> //イテレータあるけど順序保持しないset
#include<utility>       //pair
#include<vector>        //可変長配列

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
typedef vector<vector<ld>> vvld;
typedef vector<vector<string>> vvs;
typedef vector<vector<bool>> vvb;
const ll MOD = 1000000007;
const ll INF = 1000000000000000000;
#define rep(i,n) for(int i=0;i<n;i++)
#define repl(i,s,e) for(int i=s;i<e;i++)
#define reple(i,s,e) for(int i=s;i<=e;i++)
#define revrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

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

    int N, W;
    cin >> N >> W;

    vll w(N), v(N);
    rep(i, N) cin >> w[i] >> v[i];

    //dp[i][j] := i番目までの品物で重さをj以下とするときの価値の最大値
    vvll dp(N + 1, vll(W + 1, 0));

    rep(i, N)
    {
        reple(j, 0, W)
        {
            chmax(dp[i + 1][j], dp[i][j]);

            if (j < W) chmax(dp[i + 1][j + 1], dp[i + 1][j]);

            if (j + w[i] <= W)
            {
                chmax(dp[i + 1][j + w[i]], dp[i][j] + v[i]);
            }
        }
    }

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

    return 0;
}

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

const int M = 1000005; 

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];

    sort(a.begin(), a.end());

    vector<int> cnt(M);
    for (int x : a) {
        if (cnt[x] != 0) {
            cnt[x] = 2;
            continue;
        }
        for (int i = x; i < M; i += x) cnt[i]++;
    }

    int ans = 0; 
    for (int x : a) {
        if(cnt[x] == 1) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 8016
// AtCoder template
// 最近sabaがかまってくれないからキレて暴れてる
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i = 0; i < n; ++i)

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

    int n; cin >> n;
    vector<string> s(n); rep(i,n) cin >> s[i];
    unordered_map<string, int> m;
    rep(i,n){
        int tmpl = 0, tmpr = 0;
        rep(j,s[i].size()){
            if(s[i][j] == '('){
                tmpl++;
            }else{
                if(tmpl !=0 ) tmpl--;
                else tmpr++;
            }
        }
        if(tmpl != 0 && tmpr == 0){
            m[s[i]] = -1100000;
        }
        if(tmpr != 0 && tmpl == 0){
            m[s[i]] = 1100000;
        }
        if(tmpl != 0 && tmpr != 0){
            m[s[i]] = tmpr - tmpl;
        }
    }
    sort(s.begin(), s.end(), [&](string a, string b){
        return m[a] < m[b];
    });
    int now = 0;
    if(s[0][0] == ')' || s[n-1][s[n-1].size()-1] == '('){
        cout << "No" << endl;
        return 0;
    }
    rep(i,n){
        rep(j,s[i].size()){
            if(s[i][j] == '(') now++;
            else now--;
            if(now < 0){
                cout << "No" << endl;
                return 0;
            }
        }
    }
    if(now == 0) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 34560
#include <bits/stdc++.h>
using namespace std;
#define DEBUG_MODE
#define endl '\n'
#ifdef DEBUG_MODE
#define DEBUG(X) debug_func(X, #X)
#define DEBUG_ENDL endl
#define DEBUG_SEPARATOR_LINE cout<<"=================\n"
#else
#define DEBUG(X) 0
#define DEBUG_ENDL 0
#define DEBUG_SEPARATOR_LINE 0
#endif
#define ALL(V) (V).begin(), (V).end()
#define ALLR(V) (V).rbegin(), (V).rend()
#define DEBUG_ENDL_S(S) ((S).size() ? "\n" : "")
template <typename T> using V = vector<T>;
template <typename T> using VV = V<V<T>>;
template <typename T, typename U> using P = pair<T, U>;
using ll = int64_t;
using PLL = P<ll, ll>;
template <typename T> const T& var_min(const T &t) { return t; }
template <typename T> const T& var_max(const T &t) { return t; }
template <typename Head, typename... Tail> const Head& var_min(const Head &head, const Tail&... tail) { return min(head, var_min(tail...)); }
template <typename Head, typename... Tail> const Head& var_max(const Head &head, const Tail&... tail) { return max(head, var_max(tail...)); }
template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); }
template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); }
void debug_func_preffix(const string &s) { if(s.size()) cout << s << " = "; }
template <typename T>
void debug_func(const T &t, const string &s = "") {
    debug_func_preffix(s);
    cout << t << DEBUG_ENDL_S(s);
}
template <typename T, typename U>
void debug_func(const P<T, U> &p, const string &s = "") {
    debug_func_preffix(s);
    cout << "(";
    debug_func(p.first);
    cout << ", ";
    debug_func(p.second);
    cout << ")" << DEBUG_ENDL_S(s);
}
template <typename T>
void debug_func(const V<T> &v, const string &s = "") {
    for(ll i = 0; i < v.size(); i++) {
        string t = s + "[" + to_string(i) + "]";
        debug_func(v[i], t);
    }
}

int main() {
    ll N, M;
    cin >> N >> M;
    V<ll> X(N);
    for(ll &e : X) cin >> e;
    VV<ll> modv(M);
    for(ll i = 0; i < N; i++) {
        ll m = X[i] % M;
        modv[m].push_back(X[i]);
    }
    V<ll> rest(M, 0);
    ll ans = 0;
    for(ll i = 0; ; i++) {
        ll j = (M - i) % M;
        if(j < i) break;
        if(i == j) {
            ans += modv[i].size() / 2;
            rest[i] = modv[i].size() % 2;
        } else {
            ll idx =  (modv[i].size() < modv[j].size() ? i : j);
            ll ridx = (modv[i].size() < modv[j].size() ? j : i);
            ans += modv[idx].size();
            rest[ridx] = modv[ridx].size() - modv[idx].size();
        }
    }
    for(ll i = 0; i < M; i++) {
        map<ll, ll> cnt;
        for(ll e : modv[i]) cnt[e]++;
        ll v = 0;
        for(const auto &e : cnt) v += e.second / 2;
        ans += min(rest[i] / 2, v);
    }
    cout << ans << endl;
    return 0;
}


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

typedef long long ll;

#define int ll
#define all(v) v.begin(), v.end()
#define reps(__i, a, b) for (int __i = a; i < b; i++)
#define rep(__i, n) reps(__i, 0, n)

const ll INF = (1ll << 60);
const ll MOD = (ll)1e9 + 7;

signed main()
{
  int n;
  cin >> n;
  switch (n % 10)
  {
  case 0:
  case 1:
  case 6:
  case 8:
    cout << "pon" << endl;
    break;
  case 2:
  case 4:
  case 5:
  case 7:
  case 9:
    cout << "hon" << endl;
    break;
  default:
    cout << "bon" << endl;
    break;
  }
}

Measured memory_bytes: 3640
#include<iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

#define sz 12
char s[sz + 2], st[sz + 3];

int main() {

	//char str[10] = { }, ans[10] = { };
	int i, j, k;
	k = 0;

	scanf("%s", &s);



	for (i = 0; s[i]; i++) {
		if (s[i] == '0')
			st[k] = '0';

		else if (s[i] == '1')
			st[k] = '1';

		else {
			if (k != 0) {
				st[k - 1] = ' ';
				k -= 2;
			}
			else k--;
		}
		k++;
	}
	i = 0;
	while (k > i)
	{
		putchar(st[i]);
		i++;
	}

	putchar('\n');

	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef float fl;
typedef long long ll;
ll X;

int main(){
    cin >> X;
    int i = 0;
    ll x = 100;
    while(x < X){
        x += x / 100;
        i++;
    }
    cout << i << endl;
    return 0;
}

Measured memory_bytes: 3632