akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
#define rep(i, n) for(int i = 0; i < (n); i++)

int int_len(int n) {
  int s=0;
  while(n!=0) s++, n/=10;
  return s;
}

int int_sum(int n) {
  int m=0,s=0,a=n;
  while(a!=0) s++, a/=10;
  for(int i=s-1;i>=0;i--) m+=n/((int)pow(10,i))-(n/((int)pow(10,i+1)))*10;
  return m;
}

int fac(int n){
  int m=1;
  while(n>=1) m*=n,n--;
  return m;
}

int vec_sum(vector<int> v){
  int n=0;
  for(int i=0;i<v.size();i++) n+=v[i];
  return n;
}
///////////////////////////
int main() {
  int n,m,count=0;
  cin>>n>>m;
  vector<string> a(n),b(m);
  bool flag=false;
  rep(i,n) cin>>a[i];
  rep(i,m) cin>>b[i];
  for(int i=0;i<n-m+1;i++){
    for(int j=0;j<n-m+1;j++){
      
      
      for(int k=0;k<m;k++){
        
        for(int l=0;l<m;l++){
          if(a[i+k][j+l]==b[k][l]) count++;
        }
        
      }
      
      if(count==m*m){
        cout<<"Yes"<<endl;
        return 0;
      }else{
        count=0;
      }
      
      
      
    }
  }
  cout<<"No"<<endl;
  
  
}
///////////////////////////

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
#include<bitset>
#include<queue>
#include<set>
#include<map>
using namespace std;

#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define ROF(i,b,a) for (int i=(b);i>(a);--i)
#define REP(i,n) FOR(i,0,n)
#define PER(i,n) ROF(i,n-1,-1)

typedef int i32;
typedef long long int i64;
typedef unsigned long long int ui64;
typedef float f32;
typedef double f64;
typedef long double f128;
typedef pair<int,int> Pi;

constexpr int INF = 1e9 + 7;
constexpr int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};

int main() {
    int c[3][3]; REP(i,3) REP(j,3) cin>>c[i][j]; 
    string ans="Yes";
    int tmp[3] = {0,0};
    REP(i,3) REP(j,3) tmp[i] += c[i][j];
    REP(i,2) if((tmp[i+1]-tmp[i])%3!=0) ans = "No";
    REP(i,3) REP(j,3) tmp[i] += c[j][i];
    REP(i,2) if((tmp[i+1]-tmp[i])%3!=0) ans = "No";
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long int lint;

#define PI acos(-1)
#define INF64 1LL << 60
#define INF32 1 << 29
#define all(a) (a).begin(), (a).end()
#define INV ((long long int)1000000007)

using namespace std;

void execute()
{
	int r, g, b;
	cin >> r >> g >> b;
	if ((g * 10 + b) % 4 == 0)
	{
		cout << "YES" << endl;
	}
	else
	{
		cout << "NO" << endl;
	}
	return;
}

int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	execute();

	int stop;
	cin >> stop;

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define mk make_pair
#define fi first
#define se second
#define vll vector<ll>
#define pii pair<ll,ll>
#define vvll vector< vector<ll> >
#define pb push_back
#define sz(v) (v).size()
#define inf 1e18
#define md 1000000007
#define all(v) (v).begin(),(v).end()
#define rep(i,a,b) for(ll i=a;i<b;++i)
#define tel(a){cout<<a<<"\n";}
#define tell(a,b){cout<<a<<" | "<<b<<"\n";}
#define telll(a,b,c){cout<<a<<" | "<<b<<" | "<<c<<"\n";}
#define teln(v,n){cout<<"v- ";rep(i,0,n)cout<<v[i]<<" ";cout<<"\n";}
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
#define M 1000010

int main(){
	IOS;
	ll n;cin>>n;
	ll ans=3*n*n;
	cout<<ans;
	
	
	return 0;
}



Measured memory_bytes: 256
#include <stdio.h>

int main(void){
  int i,a;
  int o,t,s;
  o=0;t=0;s=0;
  for(i=0;i<10;i++){
    scanf("%d",&a);
    if(a>=o){s=t;t=o;o=a;}
    else if(a>=t){s=t;t=a;}
    else if(a>=s){s=a;}
  }
  printf("%d\n",o);
  printf("%d\n",t);
  printf("%d\n",s);
  return 0;
}

Measured memory_bytes: 600
import sys
from collections import Counter
from collections import deque
import math
import bisect
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

s=input()
n=len(s)
ans=0
for i in range(n-1):
    if s[i]!=s[i+1]:
        ans+=1
print(ans)

Measured memory_bytes: 3564
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <queue>

using namespace std;

int main() {
  int n, h, w;
  cin >> n >> h >> w;

  int ans = (n - h + 1) * (n - w + 1);
  cout << ans << endl;

  return 0;
}

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

using namespace std;

#define INF 2000000000
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define ll long long

int a[100010];
map<int, int>mp;

int main() {
    int N;
    cin >> N;
    rep(i, N) {
        cin >> a[i];
        mp[a[i]]++;
    }
    int cou = 0;
    for (auto itr : mp) {
        int k = itr.first;
        int n = itr.second;
        if (k > n)cou += n;
        else cou += n - k;
    }
    cout << cou << endl;
}

Measured memory_bytes: 5120
#define _USE_MATH_DEFINES 
#include <cmath>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cctype>
#define rep(i,start,n) for(int i=start;i<n;i++)
#define And &&
#define Or ||
#define Lb cout<<endl
using namespace std;

int main(void) {
	double x1, x2, y1, y2;
	cin >> x1 >> y1 >> x2 >> y2;
	double dist = sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));

	cout << fixed << setprecision(8) << dist << endl;
}

Measured memory_bytes: 1280
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    char c;
    cin >> c ;
    
    if (c == 'a' || c == 'e'|| c == 'i' || c == 'o' || c == 'u'){
    
        cout << "vowel" << endl;
    }
    else { 
        cout << "consonant" << endl;
    }
}


Measured memory_bytes: 256
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
using namespace std;
#define Ma_PI 3.141592653589793
#define eps 0.00000001
#define LONG_INF 3000000000000000000
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007
#define MOD 998244353
#define REP(i,n) for(long long i = 0;i < n;++i)    
#define seg_size 524288
#define int long long
int seg_tree[seg_size*4];
int seg_sub[seg_size*4];
int seg_set(int now){
    if(seg_sub[now*2] != -1){
        seg_tree[now*2] = seg_sub[now*2];
    }
    if(seg_sub[now*2+1] != -1){
        seg_tree[now*2+1] = seg_sub[now*2+1];
    }
    seg_tree[now] = min(seg_tree[now*2],seg_tree[now*2+1]);
    if(now != 0) seg_set(now/2);
    return 0;
}
int seg_find(int now,int n_l,int n_r,int w_l,int w_r){
    if(seg_sub[now] != -1){
        seg_tree[now] = seg_sub[now];
        seg_sub[now*2] = seg_sub[now];
        seg_sub[now*2+1] = seg_sub[now];
        seg_sub[now] = -1;
    }
    if(w_l <= n_l&&n_r <= w_r) return seg_tree[now];
    if(n_r <= w_l||w_r <= n_l) return (1LL << 31LL) - 1LL;
    return min(seg_find(now*2,n_l,(n_l+n_r)/2,w_l,w_r),seg_find(now*2+1,(n_l+n_r)/2,n_r,w_l,w_r));
}
int seg_add(int now,int n_l,int n_r,int w_l,int w_r,int setting){
    if(seg_sub[now] != -1){
        seg_tree[now] = seg_sub[now];
        seg_sub[now*2] = seg_sub[now];
        seg_sub[now*2+1] = seg_sub[now];
        seg_sub[now] = -1;
    }
    if(w_l <= n_l&&n_r <= w_r){
        seg_tree[now] = setting;
        seg_sub[now*2] = setting;
        seg_sub[now*2+1] = setting;
        seg_set(now/2);
        return seg_tree[now];
    }
    if(n_r <= w_l||w_r <= n_l) return (1LL << 31LL) - 1LL;
    return min(seg_add(now*2,n_l,(n_l+n_r)/2,w_l,w_r,setting),seg_add(now*2+1,(n_l+n_r)/2,n_r,w_l,w_r,setting));
}
#undef int
int main(){
#define int long long
    int n,m;
    cin >> n >> m;
    REP(i,seg_size*4){
        seg_tree[i] = (1LL << 31LL) - 1LL;
        seg_sub[i] = -1;
    }
    REP(i,m){
        int a;
        cin >> a;
        if(a == 0){
            int b,c,d;
            cin >> b >> c >> d;
            seg_add(1,0,seg_size,b,c+1,d);
        }else{
            int b,c;
            cin >> b >> c;
            cout << seg_find(1,0,seg_size,b,c+1) << endl;
        }
    }
}


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

using namespace std;

const int MAX = 1e5 + 10;
int N;
vector<pair<int, int>> G[MAX];
int dp[MAX];

int dfs1(int now, int prev) {
    for (auto &&el : G[now]) {
        if (el.first != prev) {
            dp[now] = max(dp[now], dfs1(el.first, now) + el.second);
        }
    }
    return dp[now];
}

int dfs2(int now, int d_par, int par) {
    vector<pair<int, int>> children;
    children.emplace_back(make_pair(0, -1));
    for (auto &&el : G[now]) {
        if (el.first == par) {
            children.emplace_back(make_pair(d_par + el.second, el.first));
        } else {
            children.emplace_back(make_pair(dp[el.first] + el.second, el.first));
        }
    }
    sort(rbegin(children), rend(children));
    int ret = children[0].first + children[1].first;
    for (auto &&el : G[now]) {
        if (el.first != par) {
            int foo = children[0].second == el.first;
            ret = max(ret, dfs2(el.first, children[foo].first, now));
        }
    }
    return ret;
}

int main() {
    scanf("%d", &N);
    for (int i = 0; i < N - 1; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        G[a].emplace_back(make_pair(b, c));
        G[b].emplace_back(make_pair(a, c));
    }
    dfs1(0, -1);
    printf("%d\n", dfs2(0, 0, -1));
}



Measured memory_bytes: 27804
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
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 ll INF = 1e9;

ll dp[10005];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int h, n;
    cin >> h >> n;
    rep(i,10005) dp[i] = INF;
    dp[0] = 0;
    rep(i,n){
        int a, b;
        cin >> a >> b;
        rep(j,10005){
            int id = max(0, j-a);
            chmin(dp[j], dp[id] + b);
        }
    }
    cout << dp[h] << endl;
    return 0;
}

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

#include <iostream>
#include <string>
using namespace std;

int main(int argc, char* argv[]){
	cin.tie(0);
	ios::sync_with_stdio(false);

	string S, T;
	cin >> S;
	cin >> T;

	int ans = 0;
	for(int i=0; i<S.size(); i++){
		if(S[i] != T[i]){
			ans++;
		}
	}
	printf("%d\n", ans);
	return 0;

}

Measured memory_bytes: 3868
// Author : SAGORIKA DAS
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define CLEAR(a) memset(a,0,sizeof a)
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define fr freopen("input.txt", "r", stdin);
#define fw freopen("output.txt", "w", stdout);
#define int long long 
typedef long long LL;
typedef pair<int,int> pii;
const int MOD = 1e9 + 7;
const int MAX = 1e5 + 5;
string s;
    
int eval(int i, int j){
  int ret = 0;
  for(int k=i;k<=j;k++){
    ret = ret*10 + (s[k]-'0');
  }
  return ret;
}

int _pow(int base, int e){
  int ret = 1;
  while(e){
    if(e%2) ret= ret*base;
    base = base*base;
    e /= 2;
  }
  return ret;
}

 main() {
    //fr;fw;
    cin >> s;
    int zero = 0, n = s.size();
    int ret = 0;
    for(int i=0;i<s.size();i++){
      for(int j=i;j<s.size();j++){
        int val = eval(i,j);
        ret += val*(_pow(2,max(i-1,zero)))*(_pow(2,max(zero,n-2-j)));
      }
    }
    cout << ret;
    return 0;
}

Measured memory_bytes: 256
n = int(input())
r = int((2*n)**.5)
if 2*n!=r*(r+1):
    print('No')
    exit()

# 三角数
res = [[]]
cnt = 1
num = 1
for i in range(r):
    l = list(range(cnt,cnt+num))
    res.append(l)
    for j,k in enumerate(l):
        res[j] += [k]
    cnt += num
    num += 1

print('Yes')
print(len(res))
for l in res:
    print(len(l),*l)


Measured memory_bytes: 9480
#include <iostream>
#include <climits>
using namespace std;
#define MAX 1e18

int main(void){
    int n;
    cin >> n;
    long long int a[100005];
    long long int sum = 1;
    long long max = MAX;
    for(int i=1; i<=n; i++){
        cin >> a[i];
        if(a[i] == 0) sum = 0;
    }
    for(int j=1; j<=n; j++){
        if(a[j] == 0)break;
        else if(sum > max / a[j]){
            sum = -1;
            break;
        }else{
            sum *= a[j];
        }
    }

    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 4316
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0;i < (int)(n);i++)
using ll = long long;
const ll MOD=1000000007;
//const ll MOD=998244353;
const long long INF = 1LL << 60;
const double pi=acos(-1.0);

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

//https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a

ll mod_pow(long long x, long long n) {
    long long ret = 1;
    while (n > 0) {
        if (n & 1) ret = ret * x % MOD;  // n の最下位bitが 1 ならば x^(2^i) をかける
        x = x * x % MOD;
        n >>= 1;  // n を1bit 左にずらす
    }
    return ret;
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  // cout << fixed << setprecision(15);

  ll N; cin>>N;
  vector<ll> A(N); rep(i,N) cin>>A[i];
  ll sum=0; rep(i,N) sum=(sum+A[i])%MOD;
  ll sum2=0; rep(i,N) sum2=(sum2+A[i]*A[i])%MOD;
  ll ans=(sum*sum-sum2)%MOD; if(ans<0) ans+=MOD;
  ans*=mod_pow(2,MOD-2); ans%=MOD;
  
  cout<<ans<<endl;
  
  return 0;
}

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

using namespace std;


int main() {
    string s, t;
    cin >> s >> t;
    int maximum = 0;
    for (int i = 0; i < s.size() - t.size() + 1; ++i) {
        int count = 0;
        for (int j = 0; j < t.size(); ++j) {
            if (s[i + j] == t[j]) {
                count++;
            }
        }
        maximum = max(maximum, count);
    }
    cout << t.size() - maximum;
    return 0;
}

Measured memory_bytes: 3624
#include<stdio.h>

int main()
{
	int num[3];
	scanf("%d%d%d",&num[0] ,&num[1] ,&num[2]);
	for (int i = 0 ; i < 2; i++ )
	{
		for(int j = i + 1 ; j<=2 ; j++)
		{
			if (num[i] > num[j])
			{
			int p = num[i];
			num[i] = num[j];
			num[j] = p;
			}
			
		}
	}
	printf("%d %d %d\n",num[0],num[1],num[2]);
	return 0;
}


Measured memory_bytes: 2036
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
constexpr int inf=1e9+7;
constexpr ll longinf=1LL<<60 ;
constexpr ll mod=1e9+7 ;

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    string s;
    cin>>s;
    rep(i,s.size()){
        if(s[i]=='P')cout<<s[i];
        else cout<<'D';
    }
    cout<<endl;
    return 0;
}

Measured memory_bytes: 3748
{-# LANGUAGE OverloadedStrings #-}

import qualified Data.ByteString.Char8 as B
import Data.Maybe (fromJust)

main :: IO ()
main = do
    [r, g, b] <- map (fst . fromJust . B.readInt) . B.words <$> B.getLine
    B.putStrLn $ if (r * 100 + g * 10 + b) `mod` 4 == 0 then "YES" else "NO"


Measured memory_bytes: 380
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<cmath>
#include<complex>
#include<deque>
#include<map>
#include<set>
#include<cstring>
#include<ctime>
using namespace std;
struct Edge{
	int to,next,Val;
}Graph[500050];
int h[200050],cnt;
void AddEdge(int x,int y,int z){
	Graph[++cnt].to=y;
	Graph[cnt].next=h[x];
	Graph[cnt].Val=z;
	h[x]=cnt;
	Graph[++cnt].to=x;
	Graph[cnt].next=h[y];
	Graph[cnt].Val=z;
	h[y]=cnt;
}
queue<int> Q;
bool Inque[200050];
int d[200050];
int n,m;
void SPFA(int st){
	for(int i=1;i<=n;i++)
		d[i]=0x3f3f3f3f;
	d[1]=0;
	Q.push(1);
	Inque[1]=1;
	while(!Q.empty()){
		int x=Q.front();
		Q.pop();
		Inque[x]=0;
		for(int i=h[x];i;i=Graph[i].next){
			int y=Graph[i].to;
			if(d[y]>d[x]+Graph[i].Val){
				d[y]=d[x]+Graph[i].Val;
				if(!Inque[y]){
					Q.push(y);
					Inque[y]=1;
				}
			}
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	int a,b;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&a,&b);
		AddEdge(a,b,1);
	}
	SPFA(1);
	if(d[n]>2)
		puts("IMPOSSIBLE");
	else puts("POSSIBLE");
}


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

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define MT make_tuple
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second

template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class T>
istream& operator>>(istream& is, vector<T>& xs){
  for(auto& x: xs)
	is >> x;
  return is;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
ostream& operator<<(ostream& os, const vector<T>& xs){
  for(unsigned int i=0;i<xs.size();++i)
	os << (i?" ":"") << xs[i];
  return os;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}
void debug(istringstream&){}
template <char sep=',', class Head, class... Tail>
void debug(istringstream& iss, Head&& head, Tail&&... tail)
{
  string name;
  getline(iss, name, ',');
  cerr << sep << name << "=" << head;
  debug(iss, forward<Tail>(tail)...);
}
#define DEBUG(...) \
  do{ \
    istringstream ss(#__VA_ARGS__); \
    debug<' '>(ss, __VA_ARGS__); \
    cerr<<endl; \
  }while(0)

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

LL dp[3010][3010];

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

  int N;
  cin >> N;
  string S;
  cin >> S;

  REP(i,N) dp[0][i] = 1;

  REP(i,N-1){
    if(S[i] == '<'){
      for(int k=0;k<N-i;++k){
        /*
        for(int kk=k;kk<N-1-i;++kk){
          (dp[i+1][kk] += dp[i][k]) %= MOD;
        }
        */
        (dp[i+1][k] += dp[i][k]) %= MOD;
        (dp[i+1][N-1-i] += MOD - dp[i][k]) %= MOD;
      }
    }
    else{
      for(int k=0;k<N-i;++k){
        /*
        for(int kk=0;kk<k;++kk){
          (dp[i+1][kk] += dp[i][k]) %= MOD;
        }
        */
        (dp[i+1][0] += dp[i][k]) %= MOD;
        (dp[i+1][k] += MOD - dp[i][k]) %= MOD;
      }
    }

    for(int ii=0;ii<=N;++ii) (dp[i+1][ii+1] += dp[i+1][ii]) %= MOD;
  }
  
  LL ans = 0;
  REP(i,N+1) ans += dp[N-1][i];
  cout << ans % MOD << endl;

  return 0;
}


Measured memory_bytes: 70784
class HeapTree
	def initialize
		@node = []
		@n = 0
	end

	private

	def from_root_swap(key)
		right = right_key(key)
		left = left_key(key)
		if  key < 0 
			return nil
		end
		if !@node[left] && !@node[right]
			return nil
		elsif @node[left] && !@node[right]
			if @node[left] > @node[key]
				@node[key], @node[left] =  @node[left], @node[key]
				from_root_swap(left)
			end
		elsif @node[right] && !@node[left]
			if @node[right] > @node[key]
				@node[key], @node[right] =  @node[right], @node[key]
				from_root_swap(right)
			end
		elsif @node[key] <= @node[left] && @node[left] >= @node[right]
			@node[key], @node[left] =  @node[left], @node[key]
			from_root_swap(left)
		elsif @node[key] <= @node[right] && @node[right] >= @node[left]
			@node[key], @node[right] =  @node[right], @node[key]
			from_root_swap(right)
		end
	end

	def from_leaf_swap(key)
		if key == 0
			return nil
		end
		parent_key = (key-1)/2
		if @node[parent_key] < @node[key]
			@node[key], @node[parent_key] = @node[parent_key], @node[key]
			from_leaf_swap(parent_key)
		end
	end

	def extract!
		num = @node[0]
		@node[0] = @node.pop
		@n -= 1
		from_root_swap(0)
		return num
	end

	def insert!(num)
		@node << num
		@n += 1
		from_leaf_swap(@n-1)
	end

	def left(key)
		@node[2*key+1]
	end

	def right(key)
		@node[2*key+2]
	end

	def left_key(key)
		2*key+1
	end

	def right_key(key)
		2*key+2
	end

	# ???????????¢?´¢
	def precedingOrderSearch(key, &func)
		if @node[key]
			func.call(key, @node[key])
			precedingOrderSearch(left(key), &func)
			precedingOrderSearch(right(key), &func)
		end
	end
	# ???????????¢?´¢
	def afterLineOrderSearch(key, &func)
		if @node[key]
			afterLineOrderSearch(left(key), &func)
			afterLineOrderSearch(right(key), &func)
			func.call(key, @node[key])
		end
	end
	#???????????¢?´¢
	def centerOrderSearch(node, &func)
		if @node[key]
			centerOrderSearch(left(key), &func)
			func.call(key, @node[key])
			centerOrderSearch(right(key), &func)
		end
	end

	public

	def insert(num)
		insert!(num)
	end

	def preceding_crawl(&func) #???hoge.precedingCrawl do |key, value| ??????????????????
		precedingOrderSearch(0, &func)
	end

 # ????????????
 def after_line_crawl(&func)
 	afterLineOrderSearch(0, &func)
 end

# ????????????
def center_crawl(&func)
	centerOrderSearch(0, &func)
end

def extract
	extract!
end

def priority_create
	i = 0
	loop{
		key = (@n-1)/2-i
		break if key < 0
		from_root_swap(key)
		i += 1
	}
end

def list
	return @node
end
end


ans = []
head = HeapTree.new
loop {
	str = gets.to_s.chomp!
	if str == "extract"
		ans << head.extract
	elsif str == "end"
		break
	else
		str = str.split
		head.insert str[1].to_i
	end
}


ans.each do |v|
	puts v
end

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

using namespace std;

using ll = long long;

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

    std::vector<ll> B(N - 1);
    std::for_each(B.begin(), B.end(), [](auto &x) { cin >> x; });

    std::vector<ll> A(N);
    A[0] = B[0];
    for (int i = 1; i < N - 1; ++i) {
        A[i] = std::min(B[i - 1], B[i]);
    }
    A[N - 1] = B[N - 2];

    cout << std::accumulate(A.cbegin(), A.cend(), 0) << endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<string.h>

using namespace std;

int a,b;
bool is(int i)
{
    int l = 0;
    while(i>0)
    {
        l += i%10;
        i/=10;
    }
    if(l>=a && l<=b)
        return 1;
    return 0;
}
int main()
{
    int n,sum=0;
    cin>>n>>a>>b;
    for(int i=1;i<=n;i++)
    {
        if(is(i))
        {
            sum+=i;
        }
    }
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
#define rep(i, a, b) for(int i=(a); i<(b); i++)
typedef long long ll;
int main(){
  ll N, X,L[101],d=0,res=1;
  cin >> N >>X;
  rep(i,0,N){
    cin >> L[i];
    d += L[i];
    if(d<=X) res++;
    //if(d > X) break;
  }
 
  cout << res<< endl;
  
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{   
	int answer = 0;
	int n;
	int v[20];
	int c[20];

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> c[i];
	}

	for (int i = 0; i < n; i++) {
		if (v[i]>c[i]) {
			answer += (v[i] - c[i]);
		}
	}
	cout << answer;
}


Measured memory_bytes: 256
#include<stdio.h>
#define INFTY (1 << 21)
#define WHITE 0
#define GRAY 1
#define BLACK 2

int n;
int M[100][100];

int prim();

int main(){
  int i, j, a;
  int P;

  scanf("%d",&n);

  for(i = 0 ; i < n ; i++){
    for(j = 0 ; j < n ; j++){
      scanf("%d",&a);
      M[i][j] = a;
      if(M[i][j] == -1) M[i][j] = INFTY;
    }
  }

  P = prim();
  printf("%d\n",P);

  return 0;
}

int prim(){
  int i, u, min;
  int d[100], p[100], color[100];
  int sum = 0;

  for(i = 0 ; i < n ; i++){
    d[i] = INFTY;
    p[i] = -1;
    color[i] = WHITE;
  }

  d[0] = 0;

  while(1){
    min = INFTY;
    u = -1;
    for(i = 0 ; i < n ; i++){
      if(min > d[i] && color[i] != BLACK){
	u = i;
	min = d[i];
      }
    }

    if(u == -1) break;
    
    color[u] = BLACK;
    for(i = 0 ; i < n ; i++){
      if(color[i] != BLACK && M[u][i] != INFTY){
	if(d[i] > M[u][i]){
	  d[i] = M[u][i];
	  p[i] = u;
	  color[i] = GRAY;
	}
      }
    }
  }

  for(i = 0 ; i < n ; i++){
    if(p[i] != -1) sum += M[i][p[i]];
  }

  return sum;
}

  



Measured memory_bytes: 2104
#include <iostream>
#include <cstdio>

using namespace std;

int N, M;
int main()
{
  cin >> N >> M;
  int tot = 0;
  int a;
  for(int i = 0; i < M; i++)
  {
    cin >> a;
    tot += a;
  }
  if(tot <= N)
    cout << N - tot;
  else
    cout << -1;
  return 0;
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
#define dhoom ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);  
typedef long long ll;
typedef long double ld;
const ll inf = 1e18;
const int nax = 2e6 + 7;
const ll mod = 1e9 + 7;
//ll tree[4 * nax];
//9uS-22RSwk7gQqh
ll gcd(ll a , ll b){
	if(b == 0) return a;
	return gcd(b , a % b);	
}
ll lcm(ll a , ll b){
	ll g = gcd(a , b);
	ll lc = (a/g) * b;
	return lc;
}
//char a[55][55];
int dx[] = {1,0,-1,0,1,1,-1,-1};
int dy[] = {0,1,0,-1,1,-1,-1,1};
ll a[100];
int main()
{
	dhoom;
	int m;
	cin >> m;
	cout << 24 + 24 - m << endl;
	return 0;
}


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

using namespace std;
const int N = 200010;
const int M = 1000010;
const int MOD = 998244353;
int _w;

int fpow( int a, int b ) {
	int c = 1;
	while(b) {
		if( b & 1 ) c = int(1LL * c * a % MOD);
		a = int(1LL * a * a % MOD);
		b >>= 1;
	}
	return c;
}

int inv( int x ) {
	return fpow(x, MOD-2);
}

void add_mod( int &a, int b ) {
	a += b;
	a -= a >= MOD ? MOD : 0;
}

void sub_mod( int &a, int b ) {
	a -= b;
	a += a < 0 ? MOD : 0;
}

int n, a[N], s[M], s2[M];

void factor( int x ) {
	for( int i = 1; i*i <= x; ++i )
		if( x % i == 0 ) {
			add_mod( s[i], x );
			add_mod( s2[i], int(1LL * x * x % MOD) );
			if( x/i != i ) {
				add_mod( s[x/i], x );
				add_mod( s2[x/i], int(1LL * x * x % MOD) );
			}
		}
}

bool vis[M];
int prime[M], pidx, miu[M];

void init() {
	miu[1] = 1;
	for( int i = 2; i < M; ++i ) {
		if( !vis[i] ) {
			prime[pidx++] = i;
			miu[i] = -1;
		}
		for( int j = 0; j < pidx; ++j ) {
			int k = i * prime[j];
			if( k >= M ) break;
			vis[k] = 1;
			if( i % prime[j] ) miu[k] = -miu[i];
			else break;
		}
	}
}

int f[M];

void add2( int &a, int b ) {
	if( b == 0 ) return;
	else if( b > 0 ) {
		add_mod(a, b);
	} else {
		sub_mod(a, -b);
	}
}

void solve() {
	int ans = 0;
	const int inv2 = inv(2);
	for( int i = 1; i < M; ++i ) {
		f[i] = int(1LL * s[i] * s[i] % MOD);
		sub_mod( f[i], s2[i] );
		f[i] = int(1LL * f[i] * inv2 % MOD);
		if( f[i] )
			for( int j = 1; j*j <= i; ++j )
				if( i % j == 0 ) {
					int tmp = int(1LL * f[i] * inv(i/j) % MOD);
					add2( ans, miu[j] * tmp );
					if( i/j != j ) {
						tmp = int(1LL * f[i] * inv(j) % MOD);
						add2( ans, miu[i/j] * tmp );
					}
				}
	}
	cout << ans << endl;
}

int main() {
	_w = scanf( "%d", &n );
	for( int i = 1; i <= n; ++i ) {
		_w = scanf( "%d", a+i );
		factor( a[i] );
	}
	init(), solve();
	return 0;
}


Measured memory_bytes: 19456
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <iostream>
#include <stdlib.h>

using namespace std;


const long long int MAX = 2000000007;
long long int dist[1001][1001]={};
long long int visit[8] = {};
int r;
long long int ans = 9223372036854775807;


int main()
{
  int i,j,k;
  int n,m;
  cin >> n >> m >> r;

  //行列を初期化
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      if(i!=j)
        dist[i][j] = MAX;
      else
        dist[i][j] = 0;
    }
  }

  //点を読み込む
  for(i=0;i<r;i++){
    int tmp;  cin >> tmp;
    visit[i] = --tmp;
  }

  //辺と重み(距離)を読み込む
  for(i=0;i<m;i++){
    int x,y;
    long long int d;
    cin >> x >> y >> d;  x--;  y--;
    dist[x][y] = d;
    dist[y][x] = d;
  }

  //各点に対して、その点を最短経路に含むパスの両端点間の距離を更新
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      for(k=0;k<n;k++){
        if( dist[j][k] > dist[j][i] + dist[i][k] ){
          dist[j][k] = dist[j][i] + dist[i][k];
        }
      }
    }
  }


  sort(visit,visit + r);

 do {
    long long int tmp = 0;
    for(i=0;i<r-1;i++)
      tmp += dist[visit[i]][visit[i+1]];

    if(tmp < ans)
      ans = tmp;
  } while ( std::next_permutation(visit,visit+r) );

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1408
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
 
const int MAX_N = int(1e5);
const int MAX_M = int(2e5);
 
template<typename numType>
inline bool updateMax(numType& old, const numType& test) {
    if (old < test) {
        old = test;
        return true;
    }
    return false;
}
 
struct Edge {
    int from, to;
 
    Edge(){}
    Edge(int from_, int to_):
        from(from_), to(to_)
    {}
};
 
int N, M;
vector<int> ids[MAX_N];
vector<Edge> graph[MAX_N];
Edge es[MAX_M];
 
int lengthFromS[MAX_N], lengthFromT[MAX_N];
 
void init() {
    scanf("%d%d", &N, &M);
    for (int i = 0; i < M; ++i) {
        int a, b;
        scanf("%d%d", &a, &b);
        --a; --b;
        es[i] = Edge(a, b);
        graph[a].push_back(Edge(a, b));
        graph[b].push_back(Edge(b, a));
    }
}
 
void solve() {
    int height = 0;
    for (int v = 0; v < N; ++v) {
        updateMax(height, lengthFromS[v]);
        for (int i = 0; i < int(graph[v].size()); ++i) {
            const Edge &e = graph[v][i];
            const int u = e.to;
            if (v < u) {
                updateMax(lengthFromS[u], lengthFromS[v] + 1);
            }
        }
    }
 
    for (int v = N - 1 ; v >= 0; --v) {
        for (int i = 0; i < int(graph[v].size()); ++i) {
            const Edge &e = graph[v][i];
            const int u = e.to;
            if (v > u) {
                updateMax(lengthFromT[u], lengthFromT[v] + 1);
            }
        }
    }
 
    for (int i = 0; i < M; ++i) {
        if (lengthFromS[es[i].from] + 1 + lengthFromT[es[i].to] == height) {
            ids[lengthFromS[es[i].from]].push_back(i);
        }
    }
 
    vector<int> ans;
    for (int i = 0; i < N; ++i) {
        if (int(ids[i].size()) == 1) {
            ans.push_back(ids[i][0]);
        }
    }
    sort(ans.begin(), ans.end());
    if (ans.empty()) {
        puts("-1");
    }
    else {
        for (int i = 0; i < int(ans.size()); ++i) {
            printf("%d\n", ans[i]+1);
        }
    }
}
 
int main() {
    init();
    solve();
    return 0;
}

Measured memory_bytes: 15884
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int r = sc.nextInt();
		if(r < 1200) System.out.println("ABC");
		else if(r < 2800) System.out.println("ARC");
		else System.out.println("AGC");
	}
}


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

int main(){
    int H,N;
    cin >> N >> H;
    vector<int> a(N),b(N);
    int a_max =0;
    int ans = 0;
    rep(i,N){
        cin >> a[i] >> b[i];
        if(a[i] > a_max) a_max = a[i];
    }
    sort(b.begin(),b.end(),greater<int>());
    rep(i,N){
        if(b[i] > a_max){
            H -= b[i];
            ans += 1;
            if( H <=  0 ){
                cout << ans << endl;
                return 0;
            }
        }
    }
    ans += (H / a_max);
    if(H % a_max != 0){
        ans += 1;
    }
    cout << ans << endl;

    return 0;
}

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

int main(){
	int N, K;
	string S;
	cin >> N >> K >> S;
	int Happy = 0;
	for(int i = 1; i < N; i++){
		if(S[i - 1] == S[i])Happy++;
	}
	
	for(int i = 0; i < K; i++){
		if(Happy + 2 <= N - 1){
			Happy += 2;
		}else if(Happy + 1 <= N - 1){
			Happy++;
		}else{
			break;
		}
	}
	
	cout << Happy << endl;
}

Measured memory_bytes: 512
#include <stdio.h>
#include <string.h>
int main(void){
    char s[1000+5], t[1000+5];
    scanf("%s", s);
    scanf("%s", t);
    
    int ns=strlen(s), nt=strlen(t);
    int ans=0;
    
    for(int i=0; i<=ns-nt; i++){
        int match=0;
        for(int j=0; j<nt; j++){
            if(s[i+j]==t[j])match++;
        }
        if(match>ans)ans=match;
    }
    printf("%d\n", nt-ans);
    return 0;
}


Measured memory_bytes: 1728
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		//List<String> list= new ArrayList<String>(Arrays.asList(s.split("")));
		//List<Integer> list=new ArrayList<Integer>();
		//Integer[] array = new Integer[m];
		int n = sc.nextInt();
		List<String> list=new ArrayList<String>();
		for(int i=0;n>i;i++) {
			String s = sc.next();
			list.add(s);
		}
		List<String> listB = new ArrayList<String>(new HashSet<>(list));
		if(listB.size()!=list.size()) {
			System.out.println("No");
			System.exit(0);
		}
		for(int i=0;list.size()-1>i;i++) {
			String s = list.get(i);
			String t = list.get(i+1);
			List<String> list_s= new ArrayList<String>(Arrays.asList(s.split("")));
			List<String> list_t= new ArrayList<String>(Arrays.asList(t.split("")));
			s = list_s.get(list_s.size()-1);
			t = list_t.get(0);
			if(!s.equals(t)) {
				System.out.println("No");
				System.exit(0);
			}
		}
		System.out.println("Yes");
	}
}

Measured memory_bytes: 21460
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#include <bits/stdc++.h>
using namespace std;

const double TL = 1.5 * CLOCKS_PER_SEC;
mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
#define clr(x, y) memset(x, y, sizeof(x))
#define forn(i, n) for (int i = 0; i < n; i++)
#define LL long long

LL a, b;

int main() {
  //auto start_clock = clock();
#ifdef LOCAL
  freopen("in", "r", stdin);
#endif
  cin >> a >> b;
  a %= b;
  cout << min(a, b - a) << endl;
  return 0;
}


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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
ll factorial(int i) {       //階乗
    if (i == 0) return 1;
    return (factorial(i - 1)) * i;
}

int main() { 
    ll a, b;
    cin >> a >> b;
    if(a > 0 && b > 0) cout << "Positive" << endl;
    else if(a * b <= 0) cout << "Zero" << endl;
    else {
        if(abs(a + b) % 2 == 0) cout << "Negative" << endl;
        else cout << "Positive" << endl;
    }
    return 0;
}

Measured memory_bytes: 3620
//
// Created by Mahmoud Rashad on 11/27/19.
//

#include <bits/stdc++.h>


using namespace std;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<pair<ii, ii>> vii;

const int MAXN = (int)1e5 + 5;
int memo[MAXN][4];
int n, k, R, S, P;
string t;
int solve(int idx, int prev) {
    if(idx >= n)
        return 0;
    int &ret = memo[idx][prev];
    if (~ret)
        return ret;
    ret = 0;
    if (prev != 1)
        ret = max(ret, solve(idx + k, 1) + (t[idx] == 's') * R);
    if (prev != 2)
        ret = max(ret, solve(idx + k, 2) + (t[idx] == 'p') * S);
    if (prev != 3)
        ret = max(ret, solve(idx + k, 3) + (t[idx] == 'r') * P);
    return ret;
}

int main() {
#ifndef ONLINE_JUDGE
//    freopen("input.txt", "r", stdin);
//    freopen("output.out", "w", stdout);
#endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0), cout.precision(10), cout << fixed;


    cin >> n >> k;
    cin >> R >> S >> P;
    cin >> t;
    memset(memo, -1, sizeof memo);
    int ans = 0;
    for (int i = 0; i < k; ++i) {
        ans += solve(i, 0);
    }
    cout << ans << '\n';
}

Measured memory_bytes: 6736
#include <bits/stdc++.h>
using namespace std;
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; }

using ll = long long;

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


int ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return 0;
}


int main() {
  long double A, B;
  ll N;
  cin >> A >> B >> N;

  ll ans = 0;

  if (B <= N) {
    ans = A - (A/B);

  } else {
    ans = A*(N/B);
  }

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

Measured memory_bytes: 3688
#include<iostream>
#include<map>
typedef long long ll;
using namespace std;
int main()
{
    ll n,m,q,r=0,ans=0;
    cin >> n >> m;
    map<ll,ll> M;
    M[0]=1;
    for(int i=0;i<n;i++)
    {
        cin >> q;
        r=(r+q)%m;
        ans+=M[r]++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4224
#include <cstdio>

int n, k, a[100010], aa, las, ans;
bool b;
char c[100010];

int main(){
	
	scanf("%d%d%s", &n, &k, c);
	for(int i = 1; i <= n; i++)
		a[i] = (c[i - 1] == 'L');
	
	aa = a[1];
	las = 1;
	for(int i = 1; i <= k; i++){
		b = false;
		for(int j = las + 1; j <= n; j++){
			if(a[j] != aa){
				a[j] = aa;
				b = true;
				ans++;
				las = j;
				continue;
			}
			if(b) break;
			ans++;
			las = j;
		}
	}
	
	for(int i = las + 1; i <= n; i++)
		if(a[i] == a[i - 1])
			ans++;
	printf("%d\n", ans);
			
	return 0;
}

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

// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

// forループ
#define REP(i,n) for(ll i=0; i<(ll)(n); ++i)

// 定数宣言
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

// グラフ表現
using Graph = vector<vector<int>>;

// グラフの辺表現
using Edge = map<pair<int,int>,int>;

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

// 最大公約数
ll gcd(ll a,ll b){
   if (a%b == 0) return(b);
   else return(gcd(b, a%b));
}

// 最小公倍数
ll lcm(ll a, ll b){
    return a*b/gcd(a, b);
}

int main()
{
    cout << fixed << setprecision(15);
    ll A, B, K;
    cin >> A >> B >> K;

    for(ll i=A; i<min(A+K, B-K+1); i++){
        cout << i << endl;
    }
    for(ll i=max(A,B-K+1); i<=B; i++){
        cout << i << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
#define LONGMAX 1e18
#define ll long long
#define dd double
#define MOD 1000000007
#define nl cout<<endl
#define rt ll Q[100005]={0}
#define mp make_pair
#define endl "\n"
#define test() ull t;cin>>t;while(t--)
#define pb push_back
#define ff first	
#define ss second
#define all(v) v.begin(),v.end()
#define s(ar,n) sort(ar,ar+n)
#define rs(ar,n) sort(ar, ar+n, greater<ll>()) 
#define oa(a,n) for(ll i=0;i<n;i++)cout<<a[i]<<" ";nl
#define cn(a,n) for(ll i=0;i<n;i++)cin>>a[i];
#define ov(a,n) for(ll i=n-1;i>=0;i--)cout<<a[i]<<" ";nl
#define maxa(ar,N) *max_element(ar,ar+N)
#define mina(ar,N) *min_element(ar,ar+N)
#define INF 1e9
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
ll powe(ll x,ll y){ll res=1;while(y>0){if(y&1)res=res*x;y=y>>1;x=x*x;}return res;}
ll mpowe(ll n,ll m){if(m==0)return 1;ll t=powe(n,m/2);t%=MOD;if(m%2==0)return (t*t)%MOD;return (((t*t)%MOD)*n)%MOD;}
ll logtwo(ll n){if(n==1)return 0;return logtwo(n/2)+1;}
void ceilsearch(ll ar[],ll low,ll high,ll x,ll &y){ll mid=(low+high)/2;if(low>high)return;if(ar[mid]>=x){y=mid;ceilsearch(ar,low,mid-1,x,y);}else{ceilsearch(ar,mid+1,high,x,y);}}
int main()
{
	fastio();
	ll N;
	cin>>N;
	ll ar[10][10];
	for(ll i=1;i<10;i++)
	{
	    for(ll j=1;j<10;j++)
	    {
	        ar[i][j]=0;
	        if(i==j&&i<=N)
	            ar[i][j]++;
	        for(ll k=1;k<7;k++)
	        {
	            ll f=i*powe(10,k)+j;
	            if(f>N)
	                break;
	            ll x=min((N+1-f+9)/10,powe(10,k-1));
	            ar[i][j]+=x;
	        }
	    }
	}
	ll ans=0;
	for(ll i=1;i<10;i++)
	{
	    for(ll j=1;j<10;j++)
	    {
	        ans+=ar[i][j]*ar[j][i];
	    }
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 256
// C
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
// #include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

using namespace std;
typedef long long int ll;
typedef unsigned long long ull;
typedef long double ld;
#define REP(i,n) for(ll i=0; i<(n); i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define ALL(n) begin(n),end(n)
#define IN(a, x, b) (a<=x && x<b)
#define INIT std::ios::sync_with_stdio(false);std::cin.tie(0);
template<class T> inline T CHMAX(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T CHMIN(T & a, const T b) { return a = (a > b) ? b : a; }

const long double EPS = 1e-10;
const long long INF = 1e18;
const long double PI = acos(-1.0L);
const long long MOD = 1000000007;

ll numbers[100010];

int main(void){
    ll n;
    ll k;
    cin >> n >> k;
    REP(i, n){
        ll a;
        ll b;
        cin >> a >> b;
        numbers[a] += b;
    }
    ll i =0;
    ll ans=0;
    while(true){
        if(numbers[i] >= k){
            ans = i;
            break;
        }
        k -= numbers[i];
        i++;
    }
    cout << ans << endl;
    return 0;
}

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

struct card{
	char suit;
	int num;
};

int card_out(vector <card> &A, int q){
    int n = A.size();
    for (int i=0; i<n; i++){
		cout << A[i].suit << " " << A[i].num << endl;
    }
    return 0;
}

int partition(vector <card> &A, int p, int r){
	int x = A[r].num;
	int i = p;
	for (int j=p; j<r; j++)
		if (A[j].num<=x){
			swap(A[j], A[i]);
			i++;
		}
	swap(A[i], A[r]);
	return i;
}

int merge(vector <card> &A, vector <card> &buf, int low, int mid, int high){
    int i=low, j=low, k=mid;
 
    while (j<mid && k<high){
        if (A[j].num <= A[k].num)
            buf[i] = A[j++];
        else
            buf[i] = A[k++];
        i++;
    }
 
    if (j<mid)
        for(int h=j; h<mid; h++,i++)
            buf[i] = A[h];
    else
        for (int h=k; h<high; h++,i++)
            buf[i] = A[h];
 
    for (int i=low; i<high; i++)
        A[i] = buf[i];
 
    return high-low;
}
 
int mergesort(vector <card> &A, vector <card> &buf, int low, int high ){
 
    int m=(high+low)/2, counter=0;
    if (low+1 >= high){
        return 0;
    }
 
    counter += mergesort(A, buf, low, m );
    counter += mergesort(A, buf, m, high );
    counter += merge(A, buf, low, m, high);
    return counter;
}

bool check(vector <card> &A, vector <card> &B){
	bool f = true;
	for (int i=0; i<(int)A.size(); i++)
		if (A[i].suit != B[i].suit || A[i].num != B[i].num){
			f = false;
			break;
		}
	return f;
}
int quicksort(vector <card> &A, int p, int r){
	if (p<r){
		int q = partition(A, p, r);
		quicksort(A, p, q-1);
		quicksort(A, q, r);
	}
	return 0;
}

int main(void){
	int n, q;
	cin >> n;
	vector <card> A(n), B(n), buf(n);
	for (int i=0; i<n; i++){
		cin >> A[i].suit;
		cin >> A[i].num;
	}
	B = A;
	mergesort(B, buf, 0, n);
	q = quicksort(A, 0, n-1);
	if (check(A, B)) cout << "Stable" << endl;
	else cout << "Not stable" << endl; 
	card_out(A, q);
	return 0;
}

Measured memory_bytes: 3380
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


N = I()
A = [0] + LI()

from itertools import accumulate

S = list(accumulate(A))

ans = 10**18
for i in range(2,N-1):  # AをA_1~A_i,A_(i+1)~A_Nに分割
    left = S[i]
    right = S[N]-S[i]
    # 更に各々を、和が近くなるように2分割する
    low1,high1 = 0,i
    while low1 + 1 < high1:
        mid1 = (low1+high1)//2
        if S[mid1] >= (left+1)//2:
            high1 = mid1
        else:
            low1 = mid1
    low2,high2 = i,N
    while low2 + 1 < high2:
        mid2 = (low2+high2)//2
        if S[mid2]-S[i] >= (right+1)//2:
            high2 = mid2
        else:
            low2 = mid2
    x1 = max(S[high1],S[high2]-left) - min(left-S[high1],right-S[high2]+left)
    x2 = max(S[high1],right-S[high2-1]+left) - min(left-S[high1],S[high2-1]-left)
    x3 = max(left-S[high1-1],S[high2]-left) - min(S[high1-1],right-S[high2]+left)
    x4 = max(left-S[high1-1],right-S[high2-1]+left) - min(S[high1-1],S[high2-1]-left)
    ans = min(ans,x1,x2,x3,x4)

print(ans)


Measured memory_bytes: 110892
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <fstream>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <array>
#include <vector>
#include <queue>
#include <set>
#include <cmath> // 変数名にy1が使えなくなるかも…。
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <limits>
#include <string>

typedef __int128_t int128_t;
std::istream &operator>>(std::istream& input, int128_t& value) { // int128_tの入力。入力が64bitに収まる前提。
    long long tmp; input >> tmp; value = tmp;
    return input;
}
std::ostream &operator<<(std::ostream& output, const int128_t value) { // int128_tの出力。出力が64bitに収まる前提。
    output << (long long)value;
    return output;
}

int N, A, B;

int main(int argc, char **argv) {
    std::cin >> N >> A >> B;

    std::cout << std::min(B, A*N) << std::endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <stack>

using namespace std;

int main() {
    stack<int> q;
    while (true) {
        int n;
        if (scanf("%d", &n) == EOF)
            break;

        if (n) {
            q.push(n);
        } else {
            printf("%d\n", q.top());
            q.pop();
        }
    }

    return 0;
}

Measured memory_bytes: 2700