akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(),_obj.end()
#define F first
#define S second
#define INF 1e18
#define pll pair<ll, ll> 
#define vll vector<ll>
#define deb(x) cerr<<#x<<' '<<'='<<' '<<x<<'\n'
ll n,m,a,b,c,k,temp,x,y;
const int MAXN=1e5+11;
inline ll max(ll a,ll b) {return ((a>b)?a:b);}
inline ll min(ll a,ll b) {return ((a>b)?b:a);}
inline ll gcd(ll a ,ll b) {if(b==0) return a;a%=b;return gcd(b,a);}
inline vll read(int n) {vll v(n);for (int i = 0; i < v.size(); i++)cin>>v[i];return v;}
void solveforthiscase(const int & test)
{
string s,t;
cin>>s>>t;
int cnt=0;
for(int i=0;i<s.size();i++)
if(s[i]!=t[i]) cnt++;
cout<<cnt;









return ;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // #ifndef ONLINE_JUDGE 
    // freopen("input.txt", "r", stdin); 
    // freopen("output.txt", "w", stdout); 
    // freopen("error.txt", "w", stderr); 
    // #endif 
    clock_t start, end;
    start = clock(); 
    int test=1;
    //cin>>test;
    for(int i=1;i<=test;i++)
    solveforthiscase(i);
    end = clock(); 
    long double t_t = (long double)(end - start) /(long double)(CLOCKS_PER_SEC); 
    cerr << (long double)t_t*1000<< " ms ";
}


Measured memory_bytes: 3888
s = input()
k = int(input())

if k == 1:
    print(s[0])
elif s[0] != '1':
    print(s[0])
else:
    for i in range(len(s)):
        if s[i] != '1':
            print(s[i])
            break
        if i == k - 1:
            print('1')
            break

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

int main(){
  int N;
  cin >> N;
  vector<int> diameter(N);
  for(int i=0; i<N ;i++){
    cin >> diameter.at(i);
  }
  sort(diameter.begin(),diameter.end());
  reverse(diameter.begin(),diameter.end());
  int count = 1;
  for(int i=0; i<N-1 ;i++){
    if(diameter.at(i) == diameter.at(i+1)){
      continue;
    }
    count ++;
  }
  cout << count << endl;
}

Measured memory_bytes: 256
#include "iostream"
using namespace std;
 
int main(){
 
  int A,B,K ;
  int m;
  
  cin >> K >> A >> B;
  
  m=K;
  
  while(1){
    
    if(m>B){
      cout <<"NG";
      break;
    }
       
    if(A<=m && m<=B){
      cout << "OK";
      break;
    }
    
    m += K;
  
    
  }
  return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int lmax=0, rmin=n;
    for (int i = 0; i < m; i++) {
        int l, r;
        cin >> l >> r;
        lmax = max(lmax, l);
        rmin = min(rmin, r);
    }
    cout << max(rmin - lmax + 1, 0) << '\n';
    return 0;
}


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

int m,n;
typedef pair<int,int> Pair;
Pair p[300005];
int sum[400005],add[400005];

void update(int o,int l,int r,int x,int y,int a){
	if(l>=x&&r<=y){
		sum[o]+=a*(r-l);
		add[o]+=a;
	}else{
		int mid=l+r>>1;
		if(x<mid)update(o<<1,l,mid,x,y,a);
		if(y>mid)update(o<<1|1,mid,r,x,y,a);
		sum[o]=sum[o<<1]+sum[o<<1|1]+add[o]*(r-l);
	}
}

int query(int o,int l,int r,int x,int a){
	if(r-l==1){
		return sum[o]+a;
	}else{
		int mid=l+r>>1;
		if(x<mid)return query(o<<1,l,mid,x,a+add[o]);
		else return query(o<<1|1,mid,r,x,a+add[o]);
	}
}

bool comp(Pair a,Pair b){
	return a.second-a.first<b.second-b.first;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&p[i].first,&p[i].second);
    sort(p+1,p+n+1,comp);
    int i=1;
    for(int d=1;d<=m;d++){
        while(i<=n&&p[i].second-p[i].first+1<d){
            update(1,1,m+1,p[i].first,p[i].second+1,1);
            i++;
        }
        int ans=n-i+1;
        for(int k=d;k<=m;k+=d)
            ans+=query(1,1,m+1,k,0);
        printf("%d\n",ans);
    }
    return 0;
}

Measured memory_bytes: 5888
import math
import random
import sys

sys.setrecursionlimit(10**7)
input = sys.stdin.readline
MAX_INT = 2**62-1


def main():
    def check(num, k):
        mod = num % k
        if mod == 1:
            return True
        if mod:
            return False
        exp = k
        while num % exp == 0:
            num //= exp
            exp *= exp
        return check(num, k)

    N = int(input())
    ans = 2
    for i in range(2, round(N**0.5)+1):
        ans += ((N-1) % i == 0) * 2
        if N % i == 0:
            ans += check(N, i)

    print(ans - (round((N-1)**0.5)**2 == N-1))


if __name__ == "__main__":
    main()


Measured memory_bytes: 4336
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
#define int long long
#define x first
#define y second
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ve vector
#define forn(i,n) for(int i=0;i<(int)n;i++)
#define pb push_back
#define sz(a) (int)(a.size())
//using namespace __gnu_pbds;
using namespace std;

// // // functions: find_by_order  & order_of_key
// typedef tree<
// int,
// null_type,
// less<int>,
// rb_tree_tag,
// tree_order_statistics_node_update>
// ordered_set;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;

const int inf=(int)2e9;
const long long mod=1000000007; //1E9+7
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};

ll powmod(ll a,ll p){
	ll ans=1;
	while(p){
		if(p&1) ans*=a;
		p/=2;a*=a; ans%=mod;a%=mod;
	}
	return ans;
}
ll mdinv(ll a){return powmod(a,mod-2); }

const int N=1e5+10;
vi adj[N];
bool vis[N];
int d[N];
void dfs(int i){
	vis[i]=1;
	d[i]=-1;
	for(int v:adj[i]){
		if(!vis[v]) dfs(v);
		d[i]=max(d[i],d[v]);
	}
	d[i]++;
}
signed main(){
	IOS
	int n;cin>>n;
	int m;cin>>m;
	forn(i,m){
		int a,b;cin>>a>>b;
		adj[a].pb(b);
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		if(!vis[i]) dfs(i);
		ans=max(ans,d[i]);
	}
	cout<<ans;
}


Measured memory_bytes: 8704
#include <cstdint>
#include <iostream>
#include <iomanip>
#include <vector>

using namespace std;

int main() {
  int64_t N, K;
  cin >> N >> K;

  vector<long double> cum_sum(N + 1);
  cum_sum[0] = 0.0;
  for (size_t n = 0; n < N; ++n) {
    int64_t p;
    cin >> p;
    cum_sum[n + 1] = cum_sum[n] + ((1 + p) / 2.0);
  }
  long double res = 0.0;
  for (size_t k = 0; k <= N - K; ++k) {
    long double val = cum_sum[k + K] - cum_sum[k];
    if (res < val) {
      res = val;
    }
  }
  
  cout << setprecision(7) << res << endl;
  
  return 0;
}


Measured memory_bytes: 3328
n=int(input())
a=[0] + list(map(int,input().split()))

from collections import defaultdict
dic=defaultdict(int)
dic[0]=1
for i in range(n):
  a[i+1]=a[i+1]+a[i]
  dic[a[i+1]]+=1
  
ans=0
for val in dic.values():
  ans+=(val*(val-1))//2
print(ans)

Measured memory_bytes: 36212
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE BinaryLiterals #-}
{-# LANGUAGE MultiWayIf #-}
{-# LANGUAGE NumDecimals #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TupleSections #-}

import Control.Applicative
import Control.Arrow
import Control.Monad
import Control.Monad.ST

import Data.Char
import Data.List
import Data.Maybe

import qualified Data.ByteString.Char8 as B

import Data.Array.ST.Safe
import Data.STRef

import Debug.Trace
import Text.Printf

readInt = readLn :: IO Int
readInts = map ( fst . fromJust . B.readInteger ) . B.words <$> B.getLine
readNInts = readInt >>= flip replicateM readInt

which a b f = if f then a else b
mp [ a, b ] = ( a, b )

main = do
	[ r, d, x ] <- readInts
	mapM_ print $ take 10 $ tail $ iterate ( \x -> x * r - d ) x

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

using ll = long long;
using ld = long double;
using vi = vector<int>;
using vll = vector<ll>;
using P = pair<int, int>;

const int INF = 1e9;
const ll INFLL = 1e18;
const int MOD = 1e9 + 7;
const int NIL = -1;
const ld PI = acosl(-1);

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

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	//cout << fixed << setprecision(6);
	int k, s;
	cin >> k >> s;

	ll ans = 0;
	for(int x = 0; x <= k; x++){
		for(int y = 0; y <= k; y++){
			int z = s - x- y;
			if(z < 0 || z > k) continue;
			ans++;
		}
	}

	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
/*
    AUTHOR:hruday pabbisetty
    NIT ROURKElA
    I am too dumb to realize that i am too dumb.
*/
#include <bits/stdc++.h>
#include <tr1/unordered_map>
using namespace std;
using namespace std::tr1;
#define opt ios_base::sync_with_stdio(0)
#define lli long long int
#define ulli unsigned long long int
#define I int
#define S string
#define D double
#define rep(i,a,b) for(i=a;i<b;i++)
#define repr(i,a,b) for(i=a;i>b;i--)
#define in(n) scanf("%lld",&n)
#define in2(a,b) scanf("%lld %lld",&a,&b)
#define in3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define out(n) printf("%lld\n",n)
#define inu(a) scanf("%lld",&a)
#define outu(a) printf("%llu",a)
#define ins(s) scanf("%s",&s)
#define outs(s) printf("%s",s)
#define mod 1000000007
#define inf 100000000000000
typedef long long       ll;
typedef pair<lli,lli>  plli;
typedef vector<lli>     vlli;
typedef vector<ulli>    vulli;
typedef vector<ll>      vll;
typedef vector<string>  vs;
typedef vector<plli>     vplli;
#define MM(a,x)  memset(a,x,sizeof(a));
#define ALL(x)   (x).begin(), (x).end()
#define P(x)       cerr<<"{"#x<<" = "<<(x)<<"}"<<endl;
#define P2(x,y)       cerr<<"{"#x" = "<<(x)<<", "#y" = "<<(y)<<"}"<<endl;
#define P3(x,y,z)  cerr<<"{"#x" = "<<(x)<<", "#y" = "<<(y)<<", "#z" = "<<(z)<<"}"<<endl;
#define P4(x,y,z,w)cerr<<"{"#x" = "<<(x)<<", "#y" = "<<(y)<<", "#z" = "<<(z)<<", "#w" = "<<(w)<<"}"<<endl;
#define PP(x,i)     cerr<<"{"#x"["<<i<<"] = "<<x[i]<<"}"<<endl;
#define TM(a,b)     cerr<<"{"#a" -> "#b": "<<1000*(b-a)/CLOCKS_PER_SEC<<"ms}\n";
#define UN(v)    sort(ALL(v)), v.resize(unique(ALL(v))-v.begin())
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define sz() size()
#define nl cout<<"\n"
#define MX1 100005
#define MX2 1000005
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
lli dx[]={0,0,-1,1,-1,-1,1,1};
lli dy[]={1,-1,0,0,1,-1,-1,1};
lli power(lli a,lli b)
    {
    lli value;
    if(b==0)
        {
        return 1;
    }
    else if(b%2==0)
        {
        value=power(a,b/2)%mod;
        return(value*value)%mod;
    }
    else
        {
        value=power(a,b/2)%mod;
        return ((a*value)%mod*(value))%mod;
    }
}
int main()
{
      /*  #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
        #endif*/
    opt;
    lli n,m;
    cin>>n>>m;
    if(n>=2 and m>=2)
    {
        cout<<(m-2)*(n-2);
        exit(0);
    }
    if(n==1 and m==1)
    {
        cout<<1;
        exit(0);
    }
    if(n==1)
    {
        cout<<max(0LL,m-2);
    }
    else if(m==1)
    {
        cout<<max(0LL,n-2);
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
const int INF=1e9,MOD=1e9+7,ohara=1e6+10;
const ll LINF=1e18;
using namespace std;
    
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl
#define doublecout(a) cout<<fixed<<setprecision(15)<<a<<endl;
#define Cerr(x) cerr<<(x)<<endl
#define fi first
#define se second
#define P pair<ll,ll> 
#define m_p make_pair
#define V vector<ll> 
#define U_MAP unordered_map<ll,ll>
#define pq priority_queue<ll>
#define rpq priority_queue<ll,vector<ll>,greater<ll>>
#define p_b push_back
    
ll n,cnt,ans,a,b,c,d,tmp,tmpp,m,h,w,x[ohara],y[ohara],sum,pos,k,t[ohara];
ld doua;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};
    
//-------------------------↓↓↓↓↓↓------------------------
    
//------ 自分を天才だと信じる ------
    
int main(void){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    
    cin>>n;
    rep(i,n)cin>>t[i]>>x[i]>>y[i];
    rep(i,n){
        ll kyori=(i==0 ? x[i]+y[i] : abs(x[i]-x[i-1])+abs(y[i]-y[i-1]) );
        if(kyori>(i==0 ? t[i] : t[i]-t[i-1] )){
            Cout("No");
            return 0;
        }
        else{
            if(((i==0 ? t[i] : t[i]-t[i-1] ))%2==kyori%2)continue;
            Cout("No");
            return 0;
        }
    }
    Cout("Yes");
    return 0;
}

Measured memory_bytes: 9216
import core.bitop;
import std.algorithm;
import std.ascii;
import std.bigint;
import std.conv;
import std.functional;
import std.math;
import std.numeric;
import std.range;
import std.stdio;
import std.string;
import std.random;
import std.typecons;

alias sread = () => readln.chomp();
alias Point2 = Tuple!(long, "y", long, "x");

T lread(T = long)()
{
    return readln.chomp.to!T();
}

T[] aryread(T = long)()
{
    return readln.split.to!(T[])();
}

void scan(TList...)(ref TList Args)
{
    auto line = readln.split();
    foreach (i, T; TList)
    {
        T val = line[i].to!(T);
        Args[i] = val;
    }
}

void minAssign(T, U = T)(ref T dst, U src)
{
    dst = cast(T) min(dst, src);
}

void maxAssign(T, U = T)(ref T dst, U src)
{
    dst = cast(T) max(dst, src);
}

void main()
{
    long x, t;
    scan(x, t);
    writeln((x - t).max(0));
}


Measured memory_bytes: 256
N=int(input())
A=list(map(int,input().split()))
x=dict()
for i in range(N):
    if A[i] in x:
        x[A[i]]+=1
    else:
        x[A[i]]=1
sm=0
for idx in x:
    sm+=((x[idx]-1)*x[idx])//2
    #y[idx]=((x[idx]-1)*x[idx])//2
ans=[]
#print(x)
for i in range(N):
    a=sm-(x[A[i]]-1)
    ans.append(a)
for i in range(N):
    print(ans[i])

Measured memory_bytes: 94796
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
data = [0]*(N+1)
for x in range(1,10**2+1):
    for y in range(1,10**2+1):
        for z in range(1,10**2+1):
            ans = x**2+y**2+z**2+x*y+y*z+z*x
            if ans<= N:
                data[ans]+=1
            else:
                break
for i in range(1,N+1):
    print(data[i])

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

int main() {
  int N;
  cin >> N;
  vector<int> a(N);
  for (int i = 0; i < N; i++) cin >> a[i];
  sort(a.begin(), a.end());
  int it = 0;
  for (int i = 0; i < N - 1; i++) {
    if (abs(a[N - 1] / 2. - a[i]) <= abs(a[N - 1] / 2. - a[it])) it = i;
  }
  cout << a[N - 1] << " " << a[it] << endl;
}


Measured memory_bytes: 640
#include <algorithm>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define ALL(v) (v).begin(), (v).end()
#define SP cout << fixed << setprecision(10)
const int INF = (int)1e9;
const int MOD = (int)1e9 + 7;
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

int main(void) {
    // code
    string s;
    cin >> s;
    int n = s.size();

    ll dp[100010][4] = {};
    for (int i = n; i >= 0; --i) {
        for (int j = 3; j >= 0; --j) {
            if (i == n) {
                dp[i][j] = (j == 3 ? 1 : 0);
            } else {
                dp[i][j] = dp[i + 1][j] * (s[i] == '?' ? 3LL : 1LL);
                if (j < 3 && (s[i] == '?' || s[i] == "ABC"[j])) {
                    dp[i][j] += dp[i + 1][j + 1];
                }
                dp[i][j] %= MOD;
            }
        }
    }

    cout << dp[0][0] << endl;
    return 0;
}

Measured memory_bytes: 3584
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#define rep(i,n) for(int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
int main()
{
    string s, t;
    cin >> s >> t;
    int ans = 0;
    rep(i,3){
        if(s[i] == t[i]) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define fi first
#define se second
long long mo = 1000000007;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
typedef pair<ll,Pll> PlP;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<class A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}cout << "\n";}
ld PI=3.14159265358979323846;

int main(){
    ll N,A,B;
    cin >> N >> A >> B;
    vector<ll> h(N),v(N);
    ll sum = 0;
    rep(i,N){
        cin >> h[i];
    }
    ll L = 0;
    ll R = 1e9+1;
    ll diff = A-B;
    while(L+1 < R){
        ll X =(L+R)/2;
        rep(i,N){
            v[i] = max(h[i] - B*X, 0LL);
        }
        ll cnt = 0;
        rep(i,N){
            cnt += (v[i]+diff-1)/diff;
        }
        if(cnt <= X){
            R = X;
        }else{
            L = X;
        }
    }
    cout << R << endl;
    /*
    while(1){
        ll M = h.size();
        ll unit = A + B*(M-1);
        ll num = (sum + unit - 1) / unit;
        ans += num;
        cout << "a:"<< ans << endl;
        vector<ll> v;
        //priority_queue<ll> que;
        sum = 0;
        rep(i,M){
            ll t = max(h[i]-num*B, 0LL);
            if(t > 0){
                sum += t;
                v.push(t);
            }
        }
        sum = 0;
        ll L = -1; 
        ll R = 1e9+1;
        ll add = (A-B)*num;
        while(L + 1 < R){
            ll X = (L+R)/2;
            ll tmp=0;
            rep(i,ll(v.size())){
                tmp += max(v[i] - X, 0LL);
            }
            if(tmp <= add){
                R = X;
            }else{
                L = X;
            }
        }

    
    }
        /*
        rep(i,num){
            if(que.empty()){
                goto gt;
            }
            ll t = que.top();
            que.pop();
            t -= (A-B);
            if(t > 0){
                //cout << "d:" << t << endl;
                que.push(t);
            }
        }
        cout <<"e:"<<que.size() << endl;
        while(!que.empty()){
            ll t = que.top();
            que.pop();
            sum += t;
            //cout << "bb"<<endl;
            v.push_back(t);
        }

        h = v;
        if(!h.size())break;
    }
    gt:
    cout << ans << endl;*/
}

Measured memory_bytes: 4828
#include <bits/stdc++.h>
using namespace std;
typedef bool boool;
typedef long long ll;
#define vl vector<ll>
#define vb vector<boool>
#define vs vector<string>
#define vp vector<pair<ll, ll>>
#define vvl vector<vector<ll>>
#define vvp vector<vector<pair<ll, ll>>>
#define mod 1000000007
#define all(x) x.begin(), x.end()
#define rep1(i, n) for (long long i=0; i<(long long)(n); i++)
#define rep2(i, s, e) for (long long i=(s); i<(long long)(e); i++)
#define GET_MACRO(_1,_2,_3,NAME,...) NAME
#define rep(...) GET_MACRO(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)

struct edge{ll to, cost;};
typedef pair<ll,ll> P;
struct graph{
  ll V;
  vector<vector<edge> > G;
  vector<ll> d;

  graph(ll n){
    init(n);
  }

  void init(ll n){
    V = n;
    G.resize(V);
    d.resize(V);
    rep(i,V){
      d[i] = mod;
    }
  }

  void add_edge(ll s, ll t, ll cost){
    edge e1, e2;
    e1.to = t, e1.cost = cost;
    e2.to = s, e2.cost = cost;
    G[s].push_back(e1);
    G[t].push_back(e2);
  }

  void dijkstra(ll s){
    rep(i,V){
      d[i] = mod;
    }
    d[s] = 0;
    priority_queue<P,vector<P>, greater<P> > que;
    que.push(P(0,s));
    while(!que.empty()){
      P p = que.top(); que.pop();
      ll v = p.second;
      if(d[v]<p.first) continue;
      for(auto e : G[v]){
        if(d[e.to]>d[v]+e.cost){
          d[e.to] = d[v]+e.cost;
          que.push(P(d[e.to],e.to));
        }
      }
    }
  }
};

int main(){
  int n, m;
  cin >> n >> m;
  graph g(n);
  rep(i, m){
    int a, b;
    cin >> a >> b;
    a--; b--;
    g.add_edge(a,b,1);
  }
  g.dijkstra(0);
  if(g.d[n-1] == 2) cout << "POSSIBLE" << endl;
  else cout << "IMPOSSIBLE" << endl;
  return 0;
}


Measured memory_bytes: 21788
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<math.h>
#define rep(i, a) for(int i = 0; i < a; i++)
using namespace std;

int main(){
	int h, w;
	while(1){
		cin >> h >> w;
		if(h == 0 && w == 0) break;
		rep(i, h){
			rep(j, w){
				if(i % 2 == 0)
					if(j % 2 == 0) cout << "#";
					else cout << ".";

				else if(i % 2 == 1)
					if(j % 2 == 0) cout << ".";
					else cout << "#";
			}
		cout << endl;
		}
	cout << endl;
	}
}

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

int main(void) {
    int64_t N,p;
    int64_t wrong = 0;
    cin >> N;
    for(int i=0;i<N;i++) {
        cin >> p;
        if((i+1) != p) wrong++;
    }

    if((!wrong) || (wrong == 2)) cout << "YES\n";
    else cout << "NO\n";
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
char in[10];
 
int main(){
    int a, b;
    cin >> a >> b;
    
    for(int i=0;i<b;i++)    // aをb回
        in[i] = '0' + a;
    string S = in;
    for(int i=0;i<a;i++)    // bをa回
        in[i] = '0' + b;
    string T = in;
    
    cout << min(S, T) << endl;

}

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

using namespace std;

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

  int N,M; cin>>N>>M;
  vector<int> was(N);
  int wa = 0;
  for (int i = 0; i < M; i++) {
    int p; cin>>p;
    p--;
    string s; cin>>s;
    if (was[p] == -1) {
      continue;
    } else {
      if (s == "AC") {
        wa += was[p];
        was[p] = -1;
      } else {
        was[p]++;
      }
    }
  }
  int ac = 0;
  for (auto w : was) {
    if (w == -1)
      ac++;
  }
  cout << ac << " " << wa << endl;

  return 0;
}


Measured memory_bytes: 640
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#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;

//マクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000 //10^12
#define MOD 10000007 //10^9+7
#define MAXR 100000 //10^5:最大のrange(素数列挙などで使用)

int main(void){
    ll n;
    cin >> n;
    ll min_step = INF;
    FOR(i, 1, 1000000) {
        if(n%i != 0) continue;
        min_step = min(min_step, (i-1)+(n/i-1));
    }
    cout << min_step << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <time.h>
#include <random>
#include <string>
#include <cassert>
#include <vector>
#include <ostream>
#include <istream>
#include <stack>
#include <deque>
#include <queue>
#include <functional>
#include <chrono>
#include <stack>

using namespace std;

#define int long long
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define pii pair<int, int>
#define ld long double

ostream& operator<< (ostream &out, const vector<int> &b) {
    for (auto k : b) out << k << " ";
    return out;
}

istream& operator>> (istream& in, pii& b) {
    in >> b.first >> b.second;
    return in;
}

ostream& operator<< (ostream& out, const pii& b) {
    out << "{" << b.first << ", " << b.second << "}";
    return out;
}

template <typename T1, typename T2> inline bool chkmin(T1 &x, const T2 &y) {if (x > y) {x = y; return 1;} return 0;}
template <typename T1, typename T2> inline bool chkmax(T1 &x, const T2 &y) {if (x < y) {x = y; return 1;} return 0;}


#ifdef LOCAL
    #define dbg(x) cout << #x << " : " << (x) << "\n";
    const int INF = 1e18;
    // const int mod = 2600000069;
    // const int p = 10;
#else
    #define dbg(x) 57
    const int INF = 1e18;
    // const int mod = 2600000069;
    // const int p = 179;
#endif

const ld PI = acos(-1);

#define time clock() / (double) CLOCKS_PER_SEC

// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC target("sse,sse2,sse3,sse3,sse4")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("fast-math")
// #pragma GCC target("avx2")  
// #pragma GCC optimize("section-anchors")
// #pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
// #pragma GCC optimize("vpt")
// #pragma GCC optimize("rename-registers")
// #pragma GCC optimize("move-loop-invariants")
// #pragma GCC optimize("unswitch-loops")
// #pragma GCC optimize("function-sections")
// #pragma GCC optimize("data-sections")

mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());

const int mod = 998244353;

void add(int& a, int b) {
    b %= mod;
    a += b;
    if (a >= mod) a -= mod;
}

void sub(int& a, int b) {
    b %= mod;
    a -= b;
    if (a < 0) a += mod;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    cin >> n >> k;
    vector<pii> a(n);
    for (int i = 0; i < k; i++) {
        cin >> a[i].first >> a[i].second;
    }
    vector<int> dp(n, 0);
    dp[0] = 1;
    vector<int> sum(k, 0);
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < k; j++) {
            if (i - a[j].first >= 0) {
                add(sum[j], dp[i - a[j].first]);
            }
            if (i - a[j].second - 1 >= 0) {
                sub(sum[j], dp[i - a[j].second - 1]);
            }
        }
        for (int j = 0; j < k; j++) {
            add(dp[i], sum[j]);
        }
    }
    cout << dp[n - 1];
}
/*

*/

Measured memory_bytes: 7944
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
import sys
input=sys.stdin.readline
n,m,k = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(m)]
cd = [list(map(int,input().split())) for i in range(k)]
num = [0]*(n+1)
g = [[] for i in range(n+1)]
uf = UnionFind(n+1)
for a,b in ab:
  g[a].append(b)
  g[b].append(a)
  uf.union(a,b)
for c,d in cd:
  if uf.same(c,d) == True:
    g[c].append(d)
    g[d].append(c)
for i in range(1,n+1):
  print(uf.size(i)-len(g[i])-1,end=" ")


Measured memory_bytes: 65748
N = int(input())

s = [[0 for i in range(10)] for i in range(10)]
#print(s)

for i in range(N):
    s[int(str(i+1)[0])][int(str(i+1)[-1])] += 1
    #print(s)
ans = 0
for i in range(10):
    for j in range(10):
        ans += s[i][j]*s[j][i]

print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mod 1000000007
#define test ll t; t=1; while(t--)
typedef long long int ll;
int main() {
    FIO;
    test{
        ll n,ans=0,x,y;
        cin>>n;
        x=n%500;
        y=n/500;
        ans+=(y*1000);
        n=x;
        y=n/5;
        ans+=(y*5);
        cout<<ans<<endl;
    }
	return 0;
}

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

int main() {
	int a, b; cin >> a >> b;
	if (a == 1) a += 13;
	if (b == 1) b += 13;
	if (a > b) cout << "Alice" << endl;
	else if(a < b) cout << "Bob" << endl;
	else cout << "Draw" << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>

int main(void)
{
  int deg = 90, steps, turn;
  double x = 0.0, y = 0.0, rad;
  const double kpi = 3.14159265;

  for( ; ; )
    {
      scanf("%d,%d", &steps, &turn);
      if(steps == 0 && turn == 0){
	break;
      }
      rad = ((double)deg / 180.0) * kpi;
      x += (double)steps * cos(rad);
      y += (double)steps * sin(rad);
      deg = (deg - turn) % 360;
      if(deg < 0){
	deg += 360;
      }
    }
  printf("%d\n%d\n", (int)x, (int)y);
  return 0;
}

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

int main() {
  int N, M, X, Y;
  cin >> N >> M >> X >> Y;
  vector<int> x(N), y(M);
  for (int i=0; i<N; i++) {
    cin >> x.at(i);
  }
  for (int i=0; i<M; i++) {
    cin >> y.at(i);
  }
  // Zを全探索して1つでも条件を満たすものがあれば'No War'を出力して終了
  sort(x.begin(), x.end());
  sort(y.begin(), y.end());
  string answer = "War";
  for (int Z=X+1; Z<Y+1; Z++) {
    if (x.at(N-1)<Z && Z<=y.at(0)) {
      answer = "No War";
      break;
    }
  }
  cout << answer << endl;
}

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

using namespace std;

inline void quit(){ exit(0); }

typedef long long ll;

ll mpow(ll _x, ll _y, ll _mod){
    if(_y==0) return 1;
    if(_y==1) return _x%_mod;
    if(_y&1) return (mpow(_x, _y-1, _mod)*_x)%_mod;
    ll _tmp = mpow(_x, _y>>1, _mod);
    return (_tmp*_tmp)%_mod;
}

int n, k;
int arr[200002];
int minValue[200002], maxValue[200002];
set<int> st;
int ans;

bool isGood[200002];
int goodCnt=1;

int parent[200002];
int find(int x){
    if(parent[x] == x) return x;
    return parent[x] = find(parent[x]);
}
void merge(int x, int y){
    x=find(x), y=find(y);
    parent[x]=y;
}

vector<int> vec;

int main(){
    scanf("%d %d", &n, &k);
    for(int i=1; i<=n; i++){
        scanf("%d", &arr[i]);
        parent[i] = i;
    }

    for(int i=2; i<=n; i++){
        if(arr[i-1] < arr[i]) goodCnt++;
        else goodCnt = 1;
        if(goodCnt >= k) isGood[i-k+1] = 1;
    }

    for(int i=1; i<k; i++) st.insert(arr[i]);
    for(int i=1; i<=n-k+1; i++){
        if(i!=1) st.erase(arr[i-1]);
        st.insert(arr[i+k-1]);

        minValue[i] = *(st.begin());
        maxValue[i] = *(st.rbegin());
    }

    for(int i=1; i<n-k+1; i++){
        if(arr[i] == minValue[i] && arr[i+k] == maxValue[i+1]){
            merge(i, i+1);
        }
    }

    for(int i=1; i<=n-k+1; i++){
        if(i>k && isGood[i-k]) vec.push_back(i-k);
        if(isGood[i]){
            if(vec.empty()) continue;
            merge(vec[0], i);
            while(vec.size() > 1){
                merge(vec.back(), i);
                vec.pop_back();
            }
        }
    }

    for(int i=1; i<=n-k+1; i++){
        if(find(i) == i) ans++;
    }

    printf("%d", ans);
}


Measured memory_bytes: 11136
use std::io;
use std::cmp;
use std::collections::HashSet;

fn read_line() -> String {
	let mut line = String::new();
	let _ = io::stdin().read_line(&mut line);
	line.trim().to_string()
}

fn rd() -> Vec<String> {
	let mut vs : Vec<String> = vec![];
	for s in read_line().as_str().split(' ') {
//		println!("A {}", s);
		vs.push(s.to_string())
	}
	vs
}

fn to_i(s : &str) -> Result<usize, std::num::ParseIntError> {
	s.parse::<usize>()
}

fn main() {
	loop {
		let s = read_line().as_bytes().to_vec();
		if s.len()==0 {
			break
		}
		let k = to_i(&rd()[0]).unwrap();
		let mut h = HashSet::new();
		for i in 0..s.len() {
			for j in 1..k+1 {
				if i+j <= s.len() {
					h.insert(&s[i..i+j]);
				}
			}
		}
//		println!("{:?}", h);
		let mut a : Vec<&[u8]> = h.iter().cloned().collect();
		a.sort();
		println!("{}", String::from_utf8(a[k-1].to_vec()).unwrap());
	}
}



Measured memory_bytes: 6396
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

void insertionsort( int a[] , int n , int g );
void shellsort( int a[] , int n );
int distance( int n );
void sequence( int m , int g[] );

int cnt = 0;

int main( void ){
	
	int n , m;
	int *a;
	int i;
	int g[100];
	
	scanf( "%d" , &n );
	
	a = (int*)malloc( n * sizeof(int) );
	if( a == 0 ){
		fprintf( stderr , "メモリ確保エラー\n" );
		exit(1);
	}
	
	for( i = 0; i < n; i++ ){
		scanf( "%d" , &a[i] );
	}

	m = distance( n );
	printf( "%d\n" , m );
	
	sequence( m , g );
	for( i = 0; i < m; i++ ){
		printf( "%d " , g[i] );
	}
	printf( "\n" );
	
	shellsort( a , n );
	
	printf( "%d" , cnt );
	printf( "\n" );
	
	for( i = 0; i < n; i++ ){
		printf( "%d\n" , a[i] );
	}
	
	free(a);
	
	return 0;

}

void insertionsort( int a[] , int n , int g ){
	
	int i , j;
	int v;
	
	for( i = g;  i < n; i++ ){
		
		v = a[i];
		j = i - g;
		
		while( j >= 0 && a[j] > v ){
			a[j+g] = a[j];
			j = j - g;
			cnt++;
		}
		a[j+g] = v;
	}
}

void shellsort( int a[] , int n ){
	
	int m;
	int g[100];
	int i;
	
	m = distance(n);
	sequence( m , g );
	
	for( i = 0; i < m; i++ ){
		insertionsort( a , n , g[i] );
	}
	
}

int distance( int n ){
	
	int m;
	
	m = (int)( log( 2 * n + 1 ) / log( 3 ) );
	
	return m;
}

void sequence( int m , int g[] ){
	
	int i;
	
	g[m-1] = 1;
	for( i = m - 2; i >= 0; i-- ){
		g[i] = g[i+1] * 3 + 1;
	}
	
}


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

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define forn(i , n) for(int i=0;i<n;i++)


int main(){
    int w;
    int h;
    int x;
    int y;
    int r;
    
    
    cin >> w >> h >> x >> y >> r;
    
    string ok = ((x + r) > w || (x - r) < 0 || (y + r) > h || (y + r) < 0) ? "No" : "Yes";
    cout << ok << endl; 
   
    return 0;
}

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

const int inf = 1000000007;
const int MOD = 1000000007;
const long long INF = 1000000000000000007;

int N, K;
string S;

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

    int u1 = 0;
    int u2 = 0;

    rep(i, N)
    {
        if (i == 0)
        {
            if (S[i] == 'L')
            {
                u1++;
            }
            else if (S[i] == 'R' && S[i + 1] == 'L')
            {
                u2++;
            }
        }
        else if (i == N - 1)
        {
            if (S[i] == 'R')
            {
                u1++;
            }
        }
        else
        {
            if (S[i] == 'R' && S[i + 1] == 'L')
            {
                u2++;
            }
        }
    }

    if (K < u2)
    {
        u2 -= K;
        cout << N - u2 * 2 - u1 << endl;
    }
    else
    {
        K -= u2;
        if (K == 0)
        {
            cout << N - u1 << endl;
        }
        else
        {
            cout << N - 1 << endl;
        }
    }
}


Measured memory_bytes: 512
n=gets.to_i
t,a=gets.split.map(&:to_i)
h=gets.split.map(&:to_i)
d=1000000
for i in 1..n do
  if (a-(t-h[i-1]*0.006)).abs<d
    d =(a-(t-h[i-1]*0.006)).abs
    p=i
  end
end
p p

Measured memory_bytes: 1788
use std::str::FromStr;
use std::fmt::Debug;
use std::cmp;
#[allow(dead_code)]
fn read_as_vec<T>() -> Vec<T>
where T: FromStr, <T as FromStr>::Err : Debug{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().split_whitespace().map(|c| T::from_str(c).unwrap()).collect()

}

#[allow(dead_code)]
fn read_as_string() -> String{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

fn main(){
    let line = read_as_vec::<i64>();
    let (a, b, c, k) = (line[0], line[1], line[2], line[3]);

    if k < a{
        println!("{}", k);
    }else if a <= k && k < a + b{
        println!("{}", a);
    }else{
        println!("{}", a - (k-a-b));

    }
}


Measured memory_bytes: 2132
/**
*    created: 23.05.2020 00:46:59
**/
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
using namespace std;

signed main() {

    cin.tie(0);
    ios_base::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;
    vector<pair<int,int>> mp(n);
    rep(i,n) {
        int a, b;
        cin >> a >> b;
        mp[i] = make_pair(a,b);
    }
    sort(mp.begin(), mp.end());
    int sum = 0;
    rep(i,n) {
        if (m <= mp[i].second) {
            sum += mp[i].first * m;
            break;
        }
        else {
            sum += mp[i].first * mp[i].second;
            m -= mp[i].second;
        }
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 1792
import sys
from collections import defaultdict
sys.setrecursionlimit(100000)

N, M = map(int, input().split())
AB = defaultdict(list)
gain = [0]*N
for i in range(N + M - 1):
    a, b = map(int, input().split())
    AB[a - 1].append(b - 1)
    gain[b - 1] += 1

ans = [None]*N
def rec(u, p):
    ans[u] = p
    for v in AB[u]:
        gain[v] -= 1
    for v in AB[u]:
        if gain[v] == 0 and ans[v] is None:
            rec(v, u)

root = gain.index(0)
rec(root, -1)

for i in range(N):
    print(ans[i] + 1)


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

#define int long long
#define fi first
#define se second
#define otp(n) cout << n;
#define ct(n) cout << n << endl;
#define cts(n) cout << n << " ";
#define cte cout << endl;
#define ctv(v) rep(i,(v).size()) ct(v[i])
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define repo(i,o,n) for(int i=o;i<n;i++)
#define repm(i,n) for(int i=n-1;i>=0;i--)
#define repv(i,v) for(int i=0;i<(v).size();i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define sperase(v,n) (v).erase(remove(all(v), n), (v).end());
#define vdelete(v) (v).erase(unique(all(v)), (v).end());
#define pb(n) push_back(n);

vector<int> kr(int a);

int n,f[100][10],p[100][11],ans=-10000000000;

main() {
    cin >> n;
    rep(i,n) rep(j,10) cin >> f[i][j];
    rep(i,n) rep(j,11) cin >> p[i][j];
    rep1(j,1023) {
        int tmp=0;
        vector<int> v=kr(j);
        rep(i,n) {
            int cnt=0;
            rep(k,10) {
                if (f[i][k] && v[k]) cnt++;
            }
            tmp += p[i][cnt];
        }
        ans = max(ans,tmp);
    }
    ct(ans)
}

vector<int> kr(int a) {
    vector<int> v;
    rep(i,10) {
        v.pb(a%2)
        a/=2;
    }
    return v;
}

Measured memory_bytes: 256
N, A, B = map(int, input().split())
ans = 0
for n in range(1, N+1):
  temp = 0
  for i in range(len(str(n))):
    temp += int(str(n)[i])
  if temp >= A and temp <= B:
    #print(n)
    ans += n
print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long

using namespace std;

const int MOD = 1e9 + 7;

void add(int &x, int y) {
    x += y;
    if(x >= MOD)
        x -= MOD;
}

int mult(int x, int y) {
    return (1LL * x * y) % MOD;
}

int main() {
    //freopen("a.in", "r", stdin);
    //freopen("a.out", "w", stdout);

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, k;
    cin >> n >> k;
    int lim = sqrt(n);
    vector<vector<int>> dp1(k + 1, vector<int> (lim + 2, 0));
    vector<vector<int>> dp2(k + 1, vector<int> (lim + 2, 0));

    for(int i = 1; i <= lim; i ++) {
        dp1[1][i] = 1;
        add(dp1[1][i], dp1[1][i - 1]);
    }
    for(int i = lim; i >= 1; i --) {
        add(dp2[1][i], max(0, n / i - max((n / (i + 1)), lim)));
        add(dp2[1][i], dp2[1][i + 1]);
    }

    for(int i = 2; i <= k; i ++) {
        for(int j = 1; j <= lim; j ++) {
            add(dp1[i][j], dp1[i - 1][lim]);
            add(dp1[i][j], dp2[i - 1][j]);
            add(dp1[i][j], dp1[i][j - 1]);

            add(dp2[i][j], mult(max(0, n / j - max((n / (j + 1)), lim)), dp1[i - 1][j]));
        }
        for(int j = lim; j >= 1; j --)
            add(dp2[i][j], dp2[i][j + 1]);
    }

    cout << (dp1[k][lim] + dp2[k][1]) % MOD;

    return 0;
}


Measured memory_bytes: 25344
#include<stdio.h>

int main(){

    char recent_char;

    while(1){

        scanf("%c", &recent_char);

        if(recent_char == '\n') break;
        if('a' <= recent_char && recent_char <= 'z'){
            printf("%c", recent_char - 32);
        }else if('A' <= recent_char && recent_char <= 'Z'){
            printf("%c", recent_char + 32);
        }else{
            printf("%c", recent_char);
        }
    }

    printf("\n");

    return 0;

}


Measured memory_bytes: 2596
#include <bits/stdc++.h>
#include <vector>
#include<math.h>
#include<string.h>
using namespace std;
#define MAX 300005
#define MOD 1000003
#define INF 1000000000000000000
#define EPS 0.0000000001
#define CHAINS 18
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(NULL)
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
int main()
{
    char S[3];
    scanf("%c%c%c",&S[0],&S[1],&S[2]);
    if(S[0]=='R'&&S[1]=='R'&&S[2]=='R')
    {
        printf("3");
    }
    else if(S[0]=='S'&&S[1]=='S'&&S[2]=='S')
    {
        printf("0");
    }
    else if((S[0]=='R'&&S[1]=='R')||(S[2]=='R'&&S[1]=='R'))
    {
        printf("2");
    }
    else
    {
        printf("1");
    }
    return 0;
}


Measured memory_bytes: 3684
#include <cstdio>
#include <vector>

int main() {
  using namespace std;
  long long n, k, res;
  scanf("%lld%lld", &n, &k);
  vector<vector<int> > tab(64, vector<int>(n + 1));

  for (int i = 1; i <= n; ++i) scanf("%d", &tab[0][i]);

  for (int i = 0; i < 61; ++i)
    for (int j = 1; j <= n; ++j) tab[i + 1][j] = tab[i][tab[i][j]];

  res = 1;
  for (int i = 61; i > -1; --i)
    if (k >= (1LL << i)) res = tab[i][res], k -= 1LL << i;

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


Measured memory_bytes: 53732
#include<iostream>
using namespace std;
int main(){
    long long n,a,b,x,bx,ans=0;
    cin>>n>>a>>b;
    cin>>bx;
    for(int i = 1; i < n; i++,bx=x){cin>>x;ans+=min((x-bx)*a,b);}
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

void solve()
{
	int a, b;
	while (cin >> a >> b)
	{
		map<int, int> Map;
		Map[a]++;
		Map[b]++;
		int c, d;
		while (cin >> c >> d)
		{
			if (c == 0 && d == 0)
			{
				map<int, int>::iterator it = Map.begin();
				while (it != Map.end())
				{
					if (it->first == 1 || it->first == 2)
					{
						if (it->second % 2 == 0)
						{
							cout << "NG" << endl;
							goto END;
						}
					}
					else
					{
						if (it->second % 2 == 1)
						{
							cout << "NG" << endl;
							goto END;
						}
					}
					++it;
				}
				break;
			}
			Map[c]++;
			Map[d]++;
		}
		cout << "OK" << endl;
	END:
		;
	}
}

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

Measured memory_bytes: 1184
N, W = map(int, input().split())
dp = [[0] * (W + 1) for i in range(0, N+1)]
for i in range(1, N+1):
    w, v = map(int, input().split())
    for j in range(0, W+1):
        if j < w:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)
print(dp[N][W])

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

const int maxValue = 100 * 1000 + 1;

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

  vector<int> w(n), v(n);
  for (int i = 0; i < n; i++)
    cin >> w[i] >> v[i];

  vector<int64_t> min_weight(maxValue + 1, -1);
  min_weight[0] = 0;

  for (int i = 0; i < n; i++) {
    for (int j = maxValue - v[i]; j >= 0 ; j--) {
      if (min_weight[j] > - 1) {
          int64_t new_weight = min_weight[j] + w[i];
          int new_val = j + v[i];
          if (min_weight[new_val] < 0)
            min_weight[new_val] = new_weight;
          else
            min_weight[new_val] = min(min_weight[new_val], new_weight);
      }
    }
  }

  int maxx = 0;
  for (int i = 0; i <= maxValue; i++) {
    if (min_weight[i] > - 1 && min_weight[i] <= m_w)
      maxx = max(maxx, i);
  }

  cout << maxx << "\n";
  return 0;
}

Measured memory_bytes: 1024
a,b = (int(x) for x in input().split())
N = 0
M = 0
A = []
B = []
for i in range(0,b):
    N += a * (10 ** i)
    A.append(a)
for j in range(0,a):
    M += b * (10 ** j)
    B.append(b)
if A[0] <= B[0]:
    print(N)
else:
    print(M)

Measured memory_bytes: 3064
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		Map<Integer, Set> lists = new HashMap<>();
		for (int i = 1; i <= M; i++) {
			int kn = sc.nextInt();
			Set<Integer> set = new HashSet<>();
			for (int j = 1; j <= kn; j++) {
				set.add(sc.nextInt());
			}
			lists.put(i, set);
		}
		Map<Integer, Integer> pMap = new HashMap<>();
		for (int i = 1; i <= M; i++) {
			pMap.put(i, sc.nextInt());
		}
		sc.close();
		int max = (int) Math.pow(2, (double) N);
		int ans = 0;
		for (int i = 0; i < max; i++) {
			String binary = Integer.toBinaryString(i);
			int len = binary.length();
			Map<Integer, Integer> ls = new HashMap<>();
			for (int k = 1; k <= M; k++) {
				ls.put(k, 0);
			}
			for (int j = 1; j <= len; j++) {
				for (int k = 1; k <= M; k++) {
					int tmp = ls.get(k);
					if (binary.charAt(len - j) == '1') {
						if (lists.get(k).contains(j)) {
							ls.put(k, tmp + 1);
						}
					}
				}
			}
			boolean bl = true;
			for (int k = 1; k <= M; k++) {
				if (ls.get(k) % 2 != pMap.get(k)) {
					bl = false;
				}
			}
			if (bl) {
				ans++;
			}

		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 25300
#include <iostream>
#include <vector>

using namespace std;

int main(){
	int t;
	cin >> t;
	vector<int> x{0, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 3, 4, 5, 6, 2, 3, 4, 5, 6};
	cout << (t / 25 + x[t % 25]) << endl;
	cin >> t;
	return 0;
}


Measured memory_bytes: 3116
N = gets.to_i
ans = 0

require 'prime'

ary = N.prime_division.map do |x, y|
  y
end

num = [*1..48].map do |n|
  n*(n+1)/2
end

ary.each do |e|
  (0..47).each do |i|
    next if e >= num[i]
    ans += i
    break if ans > 0
   end
end

puts ans

     



Measured memory_bytes: 14472
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(){
  int N;
  int *A;
  int i;

  double sum;

  scanf("%d", &N);
  getchar();

  A = (int *)malloc(N * sizeof(int));

  for(i=0; i<N; i++)scanf("%d", &A[i]);

  sum = 0.0;
  for(i=0; i<N; i++){
    sum += 1.0 / (double)A[i];
  }

  printf("%f\n", 1.0/sum);

  return 0;
}

Measured memory_bytes: 128
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

S = input().rstrip()
T = input().rstrip()

S,T

# Sの方が長くする
LS = len(S)
LT = len(T)
n = (LT + (-LT) % LS) // LS
S *= (n+1)
S = S[:LS+LT]

MOD = 10 ** 16 + 61
base = 12345
base_inv = pow(base,MOD-2,MOD) 
power = [1] * (LS+LT)
power_inv = [1] * (LS+LT)
for n in range(1,LS+LT):
    power[n] = power[n-1] * base % MOD
    power_inv[n] = power_inv[n-1] * base_inv % MOD

def to_rolling_hash(S):
    ret = [0] * len(S)
    for i,s in enumerate(S):
        ret[i] = (ret[i-1] + power[i] * ord(s)) % MOD
    return ret

S_hash = to_rolling_hash(S) + [0]
T_hash = to_rolling_hash(T)[-1] # 文字列全体

can_start = [(S_hash[i + LT - 1] - S_hash[i - 1]) * power_inv[i] % MOD == T_hash for i in range(LS)]

INF = 10 ** 18
visited = [False] * LS
dp = [None] * LS

arr = [INF] * LS

q = [(i,0) for i,bl in enumerate(can_start) if not bl]

while q:
    qq = []
    for x,d in q:
        if arr[x] == INF:
            arr[x] = d
            qq.append(((x-LT)%LS, d+1))
    q = qq

answer = max(arr)

if answer >= INF:
    answer = -1

print(answer)

Measured memory_bytes: 406368