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

int main() {
    ll w,h;
    std::cin >> w>>h;
    
    vector<ll> pw(w);
    vector<ll> ph(h);
    for (int i = 0; i < w; i++) {
        std::cin >> pw[i];
    }
    for (int i = 0; i < h; i++) {
        std::cin >> ph[i];
    }
    
    sort(pw.begin(),pw.end());
    sort(ph.begin(),ph.end());
    
    ll cntw,cnth;
    cntw = cnth = 0;
    
    ll ans = 0;
    
    while(cntw<w&&cnth<h){
        if(pw[cntw]<=ph[cnth]){
            ans += pw[cntw]*(h-cnth+1);
            cntw++;
        }else{
            ans += ph[cnth]*(w-cntw+1);
            cnth++;
        }
    }
    if(cntw==w){
        for (int i = cnth; i < h; i++) {
            ans += ph[i];
        }
    }else{
        for (int i = cntw; i < w; i++) {
            ans += pw[i];        
        }
    }
    
    std::cout << ans << std::endl;
    
}



Measured memory_bytes: 1792
import scala.io.{StdIn => in}

object Main extends App {
  val Array(a, b, c, d) = in.readLine.split(" ").map(_.toInt)
  val ans = if((c-a).abs <= d || (b-a).abs <= d && (c-b).abs <= d) "Yes" else "No"
  println(ans)
}

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

int main(){
  int N;
  cin >> N;
  if(N<=111){
    cout << "111" << endl;
  }else if(N<=222){
    cout << "222" << endl;
  }else if(N<=333){
    cout << "333" << endl;
  }else if(N<=444){
    cout << "444" << endl;
  }else if(N<=555){
    cout << "555" << endl;
  }else if(N<=666){
    cout << "666" << endl;
  }else if(N<=777){
    cout << "777" << endl;
  }else if(N<=888){
    cout << "888" << endl;
  }else{
    cout << "999" << endl;
  }
  return 0;
}

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

int main() {
	int N;
	cin >> N;
	int total = 0;
	for (int i = 1; i < N; i++) {
		for (int j = 1; j * j <= N - i; j++) {
			if ((N - i) % j == 0 && j * j == (N - i)) {
				total++;
			}
			else if ((N - i) % j == 0 && j * j != (N - i)) {
				total += 2;
			}
		}
	}
	cout << total << endl;
}

Measured memory_bytes: 3628
def get_score():
	score = 0
	for q in quads:
		a,b,c,d = q
		if arr[b] - arr[a] == c:
			score += d
	return score

def get_new_arr():
	last_update = N
	for i in reversed(range(N+1)):
		arr[i] = arr[i] + 1
		if arr[i] <= M:
			last_update = i
			break
	for i in range(last_update+1, N+1):
		arr[i] = arr[last_update]

N, M, Q = map(int, raw_input().split())

quads = []
for q in range(Q):
	quads.append(map(int, raw_input().split()))

arr = [1]*(N+1)
best_score = 0
while arr != [2]*(N+1):
	score = get_score()
	if score > best_score:
		best_score = score
	get_new_arr()

print best_score





Measured memory_bytes: 73144
#include <iostream>
#include <vector>
#include <string>
using ll = long long;
#define rep(i, n) for (ll i = 0; i < (n); i++)
using namespace std;

int main(){
  int h, w, k;
  cin >> h >> w >> k;
  vector<string> c(h);
  rep(i, h){
    cin >> c[i];
  }
  
  int ans = 0;
  rep(i, 1<<h)rep(j, 1<<w){
    int sum = 0;
    rep(a, h){
      if ((i>>a) & 1) continue;
      rep(b, w){
        if ((j>>b) & 1) continue;
        if (c[a][b] == '#') sum++;
      }
    }
    if (sum == k) ans++;
  }
  cout << ans << endl;
  
  return 0;
}

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

int main() {
  int N; cin >> N;
  map<string, int> W;
  string w; cin >> w;
  char lst = w[w.length()-1];
  W[w]++;
  for (int i = 1; i < N; i++) {
    cin >> w;
    if (W[w] != 0 || w[0] != lst) {
      cout << "No" << endl;
      return 0;
    } else {
      W[w]++;
      lst = w[w.length()-1];
    }
  }
  cout << "Yes" << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<map>
#include<numeric>
#include<set>
#include<string>
#include<utility>
#include<vector>

#define rep(i, a, n)  for(int i=a; i<n; i++)
#define per(i, a, n)  for(int i=n-1; i>=a; i--)
#define all(x)  (x).begin(), (x).end()
#define MAX 1000000007
using namespace std;
typedef long long ll;

int main(){
  string s; cin >> s;
  int a=-1, z;
  rep(i, 0, s.length()){
    if(s[i]=='A'&&a<0){
      a=i;
    }
    if(s[i]=='Z'){
      z=i;
    }
  }
  cout << z-a+1 << endl;
  return 0;
}

Measured memory_bytes: 640
//*-- ILSH --*//
#include <bits/stdc++.h>
using namespace std; 
typedef long long int ll;
#define pb push_back 
#define pop pop_back
#define mp make_pair
#define vii vector < int >
#define vll vector < ll > 
#define pii pair < int , int >
#define pll pair < ll , ll >
#define vpi vector < pii >
#define vpl vector < pll >
#define viii vector < vii >
#define vlll vector < vll >
#define fi first
#define sz size 
#define len length 
#define se second 
//const ll mod=998244353;
const ll mod = 1000000000+7;
const ll N=200000+6;
const ll inf=1e18+1e17;
ll powm(ll a,ll b){a=a%mod;ll res=1;while(b){if(b&1)res=(res*a)%mod;a=(a*a)%mod;b>>=1;}return (res%mod);}
ll modInverse(ll a,ll m){ll m0=m;ll y=0,x=1;if(m == 1)return 0;while(a> 1){ll q=a/m;ll t=m;m=a%m,a=t;t=y;y=x-q*y;x=t;}if(x<0)x+=m0;return x;}  
pair< ll ,ll > dp[3000+5][3000+5];
string s,t;
ll getdp(int n, int m)
{
	if ( n<0||m<0)
		return 0;
	if ( dp[n][m].fi!=-1)
		return dp[n][m].fi;
	if ( s[n]==t[m]){
		dp[n][m].fi++;
		int val=getdp(n-1,m-1);
		dp[n][m].fi=val+1;
		dp[n][m].se=2;
		return dp[n][m].fi;
	}
	int val1=getdp(n-1,m),val2=getdp(n,m-1);
	dp[n][m].fi=max(val1,val2);
	if ( val1>val2)
		dp[n][m].se=0;
	else
		dp[n][m].se=1;
	return dp[n][m].fi;
}
void solve() {
	cin>>s>>t;
	int n=s.len(),m=t.len();
	for ( int i=0;i<3000+2;i++)
		for (int j=0;j<3000+2;j++)
			dp[i][j]=mp( -1,0);
	getdp(n-1,m-1);
	int i=n-1,j=m-1;
	string ss;
	while ( true){
		if (s[i]==t[j])
			ss+=s[i];
		if ( dp[i][j].se==2){
			j=j-1;
			i=i-1;
		}
		else
		if ( dp[i][j].se==0)
			i=i-1;
		else
			j=j-1;
		if( i<0||j<0)
			break;
	}	
	reverse(ss.begin(),ss.end());
	cout<<ss<<'\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    //cin>>t;
    while ( t-- )
    	solve();    
}

Measured memory_bytes: 141568
S_=list(input())
T=list(input())

res=-1
ind=-1
for i in range(len(S_)-len(T)+1):
    flag=1
    for j in range(len(T)):
        if S_[i+j]=='?' or S_[i+j]==T[j]:
            continue
        else:
            flag=0
            break
    if flag:
        ind=i

if ind==-1:
    print('UNRESTORABLE')
    exit()

for t in T:
    S_[ind]=t
    ind+=1

for i in range(len(S_)):
    if S_[i]=='?':
        S_[i]='a'

print(''.join(S_))
    

Measured memory_bytes: 3064
S = input()

ans = [0 for i in range(len(S))]
cur = ["R", 0]
count = 1
for i in range(1, len(S)):
    if S[i] == cur[0]:
        count += 1
    else:
        if S[i] == "L":
            ans[i-1] += (count-1) // 2 + 1
            ans[i] += count // 2
        else:
            ans[cur[1]-1] += count // 2
            ans[cur[1]] += (count-1) // 2 + 1
        cur = [S[i], i]
        count = 1
ans[cur[1]-1] += count // 2
ans[cur[1]] += (count-1) // 2 + 1

for i in range(len(S)):
    print(ans[i], end=" ")

Measured memory_bytes: 4864
#include <stdio.h>

int main(void)
{
    int i, j;

    for (i = 1; i <= 9; ++i) {
        for (j = 1; j <= 9; ++j) {
            printf("%dx%d=%d\n", i, j, i * j);
        }
    }

    return 0;
}

Measured memory_bytes: 520
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
input=lambda :sys.stdin.buffer.readline().rstrip()
class ModInt(object):
    __MOD=10**9+7

    def __init__(self,x):
        self.__x=x%self.__MOD

    def __repr__(self):
        return str(self.__x)

    def __add__(self,other):
        return ModInt(self.__x+other.__x) if isinstance(other,ModInt) else ModInt(self.__x+other)

    def __sub__(self,other):
        return ModInt(self.__x-other.__x) if isinstance(other,ModInt) else ModInt(self.__x-other)

    def __mul__(self,other):
        return ModInt(self.__x*other.__x) if isinstance(other,ModInt) else ModInt(self.__x*other)

    def __truediv__(self,other):
        return ModInt(self.__x*pow(other.__x,self.__MOD-2,self.__MOD)) if isinstance(other, ModInt) else ModInt(self.__x*pow(other, self.__MOD-2,self.__MOD))

    def __pow__(self,other):
        return ModInt(pow(self.__x,other.__x,self.__MOD)) if isinstance(other,ModInt) else ModInt(pow(self.__x,other,self.__MOD))

    __radd__=__add__

    def __rsub__(self,other):
        return ModInt(other.__x-self.__x) if isinstance(other,ModInt) else ModInt(other-self.__x)

    __rmul__=__mul__

    def __rtruediv__(self,other):
        return ModInt(other.__x*pow(self.__x,self.__MOD-2,self.__MOD)) if isinstance(other,ModInt) else ModInt(other*pow(self.__x,self.__MOD-2,self.__MOD))

    def __rpow__(self,other):
        return ModInt(pow(other.__x,self.__x,self.__MOD)) if isinstance(other,ModInt) else ModInt(pow(other,self.__x,self.__MOD))
def resolve():
    from itertools import product
    L,R=map(int,input().split())
    D=R.bit_length()
    dp=[[[[ModInt(0)]*2 for _ in range(2)] for _ in range(2)] for _ in range(D+1)]
    dp[D][0][0][0]=ModInt(1)
    for d in range(D-1,-1,-1):
        lb=L>>d&1; rb=R>>d&1
        for i,j,m,x,y in product([0,1],repeat=5):
            ni,nj,nm=i,j,m
            if(x>y): continue
            # i:L<=X
            if(i==0 and lb>x): continue
            if(lb<x): ni=1
            # j:Y<=R
            if(j==0 and y>rb): continue
            if(y<rb): nj=1
            # m:MSB
            if(m==0 and x!=y): continue
            if(x==1 and y==1): nm=1
            dp[d][ni][nj][nm]+=dp[d+1][i][j][m];
    print(sum(dp[0][i][j][m] for i,j,m in product([0,1],repeat=3)))
resolve()

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

int main() {
  int H, W;
  cin >> H >> W;
  
  vector<string> a(H);
  
  for (int i = 0; i < H; i++) {
    cin >> a.at(i);
  }
  
  for (int i = 0; i < W + 2; i++) {
    cout << '#';
  }
  
  cout << endl;
  
  for (int i = 0; i < H; i++) {
    cout << '#' << a.at(i) << '#' << endl;
  }
  
  for (int i = 0; i < W + 2; i++) {
    cout << '#';
  }
  
  cout << endl;
  
}

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

#define ll long long

using namespace std;

int main(){
	ll n,t,ti,begin=0,end;
	ll sum=0;
	scanf("%lld %lld",&n,&t);
	for(int i=1;i<=n;i++){
		scanf("%lld",&ti);
		if(i==1){
			begin=ti;
			end=begin+t;
			sum+=end-begin;
			continue;
		}
		if(ti+t<=end){
			continue;
		}
		begin=ti;
		if(ti<end){
			begin=end;
		}
		end=ti+t;
		sum+=end-begin;
	}
	printf("%lld",sum);
	return 0;
} 

Measured memory_bytes: 128
using System;

public class Hello
{
    public static void Main()
    {
        string[] line = Console.ReadLine().Trim().Split(' ');
        var n = long.Parse(line[0]);
        var k = long.Parse(line[1]);
        Console.ReadLine();
        var res = (n -2) / (k -1) + 1;
        Console.WriteLine(res);
    }
}

Measured memory_bytes: 13152
//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")
   
//#include <x86intrin.h>
#include <bits/stdc++.h>   
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace __gnu_pbds;
using namespace std;

template<typename T> using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
     
#define F first
#define S second           
#define lb lower_bound               
#define ub upper_bound
#define pb push_back
#define pf push_front    
#define ppb pop_back
#define mp make_pair                                     
#define bpp __builtin_popcountll                                                                                        
#define sqr(x) ((x) * (x)) 
#define al 0x3F3F3F3F
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define in insert
#define ppf pop_front
#define endl '\n'
//#define int long long
 
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
 
const int mod = (int)1e9 + 7;
const int N = (int)3e5 + 123;
const ll inf = (ll)1e18 + 1;

const double pi = acos (-1.0);
const double eps = 1e-7;                  
const int dx[] = {0, 0, 1, 0, -1};
const int dy[] = {0, 1, 0, -1, 0};

int n, m, x[N], y[N], z[N], ans;
vector <int> g[N];
bool used[N];

void dfs (int v) {
   used[v] = 1;
   for (auto to : g[v])
      if (!used[to])
         dfs (to);
}

inline void boost () {                    
   ios_base :: sync_with_stdio (NULL);
   cin.tie (NULL), cout.tie (NULL);          
}                                                     

inline void Solve () {
   cin >> n >> m;
   for (int i = 1; i <= m; i ++) {
      cin >> x[i] >> y[i] >> z[i];
      g[x[i]].pb (y[i]);
      g[y[i]].pb (x[i]);
   }
   for (int i = 1; i <= n; i ++)
      if (!used[i])
         dfs (i), ans ++;
   cout << ans;
}

main () {                                       
// freopen (".in", "r", stdin);    
// freopen (".out", "w", stdout);              
   boost ();
   int tt = 1;
   //cin >> tt;   
   while (tt --) {
      Solve ();
   }                                               
   return 0;      
}
          

Measured memory_bytes: 16512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[110][10],num[10][10],fi[10];
int main() {
	ll h,w,k;
	cin>>h>>w>>k;
	if(w==1){
		cout<<1<<endl;
		return 0;
	}
	ll mod=1e9+7;
	dp[0][0]=1;
	num[2][0]=1;
	num[3][0]=1;num[3][1]=1;
	num[4][0]=2;num[4][1]=1;num[4][2]=2;
	num[5][0]=3;num[5][1]=2;num[5][2]=2;num[5][3]=3;
	num[6][0]=5;num[6][1]=3;num[6][2]=4;num[6][3]=3;num[6][4]=5;
	num[7][0]=8;num[7][1]=5;num[7][2]=6;num[7][3]=6;num[7][4]=5;num[7][5]=8;
	num[8][0]=13;num[8][1]=8;num[8][2]=10;num[8][3]=9;num[8][4]=10;num[8][5]=8;num[8][6]=13;
	fi[0]=1,fi[1]=1;
	for(int i=2;i<=8;i++)fi[i]=fi[i-2]+fi[i-1];
	for(int i=1;i<=h;i++){
		for(int j=0;j<w;j++){
			if(j)dp[i][j-1]+=num[w][j-1]*dp[i-1][j];
			dp[i][j]+=(fi[w]-(j?num[w][j-1]:0ll)-(j!=w-1?num[w][j]:0ll))*dp[i-1][j];
			if(j!=w-1)dp[i][j+1]+=num[w][j]*dp[i-1][j];
			dp[i][j-1]%=mod;
			dp[i][j]%=mod;
			dp[i][j+1]%=mod;
		}
	}
	cout<<dp[h][k-1];
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ins insert
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[8]={1,0,-1,0,1,1,-1,-1};
const ll dx[8]={0,-1,0,1,1,-1,1,-1};
ll modfac(ll a){
    ll ans=1;
    while(a>1){
        ans*=a;
        ans%=1000000007;
        a--;
    }
    return ans;
}
ll modinv(ll a,ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
}
struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n, -1) {}

    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};
ll modpow(ll a, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
int main(){
    ll n,m;cin >> n >>m;
    vvl v(10,vl(10));
    rep(i,10){
        rep(j,10){
            cin >> v[i][j];
        }
    }
    rep(k,10){
        rep(i,10){
            rep(j,10){
                v[i][j]=min(v[i][k]+v[k][j],v[i][j]);
            }
        }
    }
    ll ans=0;
    rep(i,n*m){
        ll x;cin >> x;
        if(x==-1)continue;
        ans+=v[x][1];
    }
    cout <<ans <<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)
#define DEBUG 0
#define MOD 1000000007
#define INF (1LL)<<50;
 
signed main(){
 
	lli n;
	cin>>n;
	lli k;
	cin>>k;
	vector<lli> v(n);
	REP(i,0,n)cin>>v[i];
 
	lli ans=-INF;
 
	/*まず左側でどこまでとるか*/
	for(lli i=0;i<n;i++){
 
		vector<lli> p; /*マイナスの宝石入れ*/
		lli left=i;
		lli sum=0;
 
		/*左端から宝石をとっていく*/
		for(lli ii=0;ii<left;ii++){
			sum += v[ii];
			if(v[ii]<0)p.push_back(v[ii]);
		}
 
		/*次に右端についてどこまで宝石をとるか*/
		for(lli j=0;j<=n;j++){
 
			/*操作回数が超えていたらやめる*/
			if(i+j>k)continue;
 
			/*右端からどこまでとるかについての情報を持つ*/
			/*すでにとっている宝石や、左端まで行ってしまう場合はやめる*/
			lli right=n-j;
			if(left>right)continue;
 
			/*左端で取った宝石の情報を引き継ぐ*/
			vector<lli> pp;
			lli nextSum=sum;
			REP(g,0,p.size())pp.push_back(p[g]);
 
			/*右端から宝石をとっていく*/
			for(lli jj=n-1;jj>=right;jj--){
				nextSum+= v[jj];
				if(v[jj]<0)pp.push_back(v[jj]);
			}
 
			/*マイナスの宝石入れのソートを行う、これで上からマイナスがでかい宝石を捨てれるようになる*/
			sort(pp.begin(),pp.end());
 
			/*残り操作回数*/
			lli allowCnt = k-(i+j);
 
			for(lli g=0;(g<allowCnt && g<pp.size());g++){
				nextSum -= pp[g];
			}
			ans = max(ans,nextSum);
		}
	}
 
	cout<<ans<<endl;
	return 0;
}

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

using namespace std;

typedef long long ll;
typedef long double ld;

const int Inf = 2e9;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.setf(ios::fixed); cout.precision(20);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    int n, k;
    cin >> n >> k;
    vector <int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    vector <int> dp(n, Inf);
    dp[0] = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 1; j <= k; ++j) {
            if (i + j < n) {
                dp[i + j] = min(dp[i + j], dp[i] + abs(a[i] - a[i + j]));
            }
        }
    }
    cout << dp[n - 1] << '\n';
}

Measured memory_bytes: 1024
import java.util.*;

public class Main{
  public static void main(String args[]){
    Scanner scanner = new Scanner(System.in);
    int A = scanner.nextInt();
    int B = scanner.nextInt();
    
    int K;
    boolean flg = false;
    
    /*
    * A <= B のとき A <= K <= B,
    * A > B のとき B < K < A でなければならない
    */
    
    if(A <= B){
      for(K = A; K <= B; K++){
        int minus = -1 * (A - K);
        int plus = B - K;
        
        if(minus == plus){
          System.out.println(K);
          flg = true;
          break;
        }
      }
      
    } else {
      for(K = B + 1; K < A; K++){
        int minus = -1 * (B - K);
        int plus = A - K;
        
        if(minus == plus){
          System.out.println(K);
          flg = true;
          break;
        }
      }
    }
    
    if(flg == false){
      System.out.println("IMPOSSIBLE");
    }
  }
}

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

int main(){
  int N;
  string C;
  cin >> N >> C;
  
  int l=0,r=N-1;
  for(int i=0;;i++){
    while(true){
      if(C[l]=='R'){
        l++;
        continue;
      }
      if(C[r]=='W'){
        r--;
        continue;
      }
      break;
    }
    if(l >= r){
      cout << i << endl;
      return 0;
    }
    C[l] = 'R';
    C[r] = 'W';
  }
  return 0;
}


Measured memory_bytes: 3664
import sys
import time

N, K = map(int, input().split())
town_list = list(map(int, input().split()))

queue = {}

start = -1
count = 1

now_town = 1

for i in range(K):
    if town_list[now_town - 1] in queue:
        start = town_list[now_town - 1]
        break
    queue[town_list[now_town - 1]] = count
    now_town = town_list[now_town - 1]
    count += 1

if start == -1:
    print(now_town)
    sys.exit()

roop = len(queue) - (queue[start] - 1)
before_len = queue[start]

print(list(queue.keys())[(K - before_len) % roop + before_len - 1])


Measured memory_bytes: 32316
let cnt = ref 0
let g = ref []

let print_list l =
  List.iteri (fun i n -> Printf.printf (if i = 0 then "%d" else " %d") n) l;
  print_newline ()

let print_array = Array.iter (fun n -> Printf.printf "%d\n" n)

let insertion_sort a n g =
  let rec insert j v =
    if j < 0 || a.(j) <= v then a.(j + g) <- v
    else (a.(j + g) <- a.(j); incr cnt; insert (j - g) v)
  in
  let rec doit i =
    if i >= n then ()
    else (insert (i - g) a.(i); doit (i + 1))
  in
  doit g

let generate_g n =
  let rec doit i lst =
    if i > n then lst
    else doit (3*i + 1) (i :: lst)
  in
  doit 1 []

let shell_sort a n =
  cnt := 0;
  g := generate_g n;
  let rec doit = function
    | [] -> ()
    | hd :: tl -> (insertion_sort a n hd; doit tl)
  in
  doit !g

let () =
  let n = read_int () in
  let a = Array.make n 0 in
  let rec doit i =
    if i >= n then ()
    else (a.(i) <- read_int (); doit (i + 1))
  in
  doit 0;
  shell_sort a n;
  Printf.printf "%d\n" (List.length !g);
  print_list !g;
  Printf.printf "%d\n" !cnt;
  print_array a

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

using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
//#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) ll(x.size())
typedef long long ll;
typedef pair<int, int> P;
//typedef pair<ll, ll> P;
//const double INF = 1e10;
const ll INF = 10e15;
const ll MINF = -10e10;
//const int INF = INT_MAX;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)


//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);

typedef priority_queue<P, vector<P>, greater<P>> PQ_ASK;
const int mod = 1000000007;

int main() {

    ll n, k;
    cin >> n >> k;

    ll ans = 0;

    for (ll b = 1; b <= n; b++) {

        ll p = n / b;
        ll r = n % b;
        assert(p * b + r == n);

        ll front = p * max(0ll, b - k);
        ll back = max(0ll, r - k + 1);
        ll now = front + back;

        if (k == 0) now--;

        ans += now;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>

using namespace std;

#define DEBUG_ //!!提出時にコメントアウト!!
#ifdef DEBUG_
	#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
	#define dump(x)  ; //何もしない文
#endif

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size()) //unsignedのサイズをint型に変換

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL; 

template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

const int MOD = 1e9+7;
const int MAX_N = 1e5+10;
int dp[MAX_N][3]; 

//ここから書き始める
int main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);	
    memset(dp,0,sizeof(dp));
    int N;
    cin >> N;
    int a[N],b[N],c[N];


    REP(i,N)
    {
        cin >> a[i] >> b[i] >> c[i];
    }
    dp[1][0] = a[0];
    dp[1][1] = b[0];
    dp[1][2] = c[0];

    for(int i=2; i <= N; i++)
    {
        dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + a[i-1];
        dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + b[i-1];
        dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + c[i-1];
    }

    cout << max(max(dp[N][0], dp[N][1]), dp[N][2]) << endl;


}


Measured memory_bytes: 2560
#[allow(unused_imports)]
use std::cmp::{max, min};
use std::io::{stdin, stdout, BufWriter, Write};

#[derive(Default)]
struct Scanner {
    buffer: Vec<String>,
}

impl Scanner {
    fn next<T: std::str::FromStr>(&mut self) -> T {
        loop {
            if let Some(token) = self.buffer.pop() {
                return token.parse().ok().expect("Failed parse");
            }
            let mut input = String::new();
            stdin().read_line(&mut input).expect("Failed read");
            self.buffer = input.split_whitespace().rev().map(String::from).collect();
        }
    }
}

fn main() {
    let mut scan = Scanner::default();
    let out = &mut BufWriter::new(stdout());

    let x = scan.next::<i32>();
    let y = scan.next::<i32>();
    writeln!(out, "{} {}", x*y, 2*(x+y)).ok();
}



Measured memory_bytes: 5032
#include <iostream>

using namespace std;

int main() {
  int sx, sy, tx, ty;
  cin >> sx >> sy >> tx >> ty;
  for (int i = sy; i < ty; ++i) cout << 'U';
  for (int i = sx; i < tx; ++i) cout << 'R';
  for (int i = sy; i < ty; ++i) cout << 'D';
  for (int i = sx; i < tx; ++i) cout << 'L';
  cout << 'L';
  for (int i = sy; i < ty + 1; ++i) cout << 'U';
  for (int i = sx; i < tx + 1; ++i) cout << 'R';
  cout << 'D';
  cout << 'R';
  for (int i = sy; i < ty + 1; ++i) cout << 'D';
  for (int i = sx; i < tx + 1; ++i) cout << 'L';
  cout << 'U';
  return 0;
}

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

struct Node{
    int parent,left,right;
};
int D[100],H[100];
Node binaryTree[25];
void setDepth(int u,int d){
    D[u]=d;
    if(binaryTree[u].left!=-1)
        setDepth(binaryTree[u].left,d+1);
    if(binaryTree[u].right!=-1)
        setDepth(binaryTree[u].right,d+1);
}
int setHeight(int u){
    if(binaryTree[u].left==-1&&binaryTree[u].right==-1)
        return 0;
    int h1=0,h2=0;
    if(binaryTree[u].left!=-1)
        h1=setHeight(binaryTree[u].left)+1;
    if(binaryTree[u].right!=-1)
        h2=setHeight(binaryTree[u].right)+1;
    H[u]=max(h1,h2);
    return max(h1,h2);    
}
int main(){
    int n,id,left,right;
        Node temp;
    cin>>n;
    for(int i=0;i<n;i++)
        binaryTree[i].parent=binaryTree[i].left=binaryTree[i].right=-1;
    for(int i=0;i<n;i++){
        cin>>id>>left>>right;
        binaryTree[id].left=left;
        binaryTree[id].right=right;
        binaryTree[left].parent=id;
        binaryTree[right].parent=id;
    }
    for(int i=0;i<n;i++)
        if(binaryTree[i].parent==-1)
        {
            setDepth(i,0);
            setHeight(i);
            break;
        }
    for(int i=0;i<n;i++)
    {
        cout<<"node "<<i<<": parent = "<<binaryTree[i].parent<<", sibling = ";
        if(binaryTree[i].parent==-1)
        {
            cout<<-1<<", degree = ";
        }
        else
        {
            temp=binaryTree[binaryTree[i].parent];
            if(i==temp.left)
                cout<<temp.right<<", degree = ";
            else
                cout<<temp.left<<", degree = ";
        }
        if(binaryTree[i].left==-1&&binaryTree[i].right==-1)
            cout<<0<<", depth = ";
        else if(binaryTree[i].left!=-1&&binaryTree[i].right!=-1)
            cout<<2<<", depth = ";
        else
            cout<<1<<", depth = ";
        cout<<D[i]<<", height = ";
        cout<<H[i]<<", ";
        if(binaryTree[i].parent==-1)
            cout<<"root"<<endl;
        else{
            if(binaryTree[i].left==-1&&binaryTree[i].right==-1)
                cout<<"leaf"<<endl;
            else
                cout<<"internal node"<<endl;
        }
    }
}


Measured memory_bytes: 3088
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define P pair<int,int>
using ll=int64_t;
using namespace std;
#define ketasuu(n) fixed<<setprecision(n)
#define btoe(p) p.begin(),p.end()
#define etob(p) p.rbegin(),p.rend()




int main(){
    int a,b,c; cin>>a>>b>>c;
    if(a+b>=c) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 256
//
//  main.cpp
//  atcoder_B
//
//  Created by 박다원 on 24/03/2019.
//  Copyright © 2019 박다원. All rights reserved.
//

#include <iostream>
#include <string>

using namespace std;

int main(int argc, const char * argv[])
{
    string str;
    cin >> str;
    
    int ans = 0;
    
    int tmp = 0;
    for(auto c : str)
    {
        if(c == 'A' || c == 'T' || c == 'G' || c == 'C')
        {
            tmp++;
            
        }
        else
        {
            tmp = 0;
        }
        ans = max(ans, tmp);
    }
    cout << ans << endl;
    return 0;
}


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

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

using namespace std;

int cnt;
void insertionSort(vector<int> &A,int g) {
  int n = A.size();
  REP(i,g,n) {
    int v = A[i];
    int j = i - g;
    while( j >= 0 && A[j] > v ) {
      A[j+g] = A[j];
      j = j - g;
      cnt++;
    }
    A[j+g] = v;
  }
}

void shellSort(vector<int> &A) {
  int n = A.size();
  cnt = 0;
  int m = 100;
  vector<int> G(m,1);
  int v = (n>>1);
  int ptr = 0;
  while( v ) {
    G[ptr++] = v;
    v >>= 1;
  }

  rep(i,m) insertionSort(A,G[i]);
  
  cout << m << endl;
  //cout << cnt << "<"  << pow(n,1.5)<< endl;
  rep(i,m) {
    if( i ) printf(" ");
    cout << G[i];
  } puts("");
  cout << cnt << endl;
  rep(i,n) cout << A[i] << endl;
}

void solve(vector<int> &vec) {
  shellSort(vec);
}

int main() {
  if( 0 ) {
    srand((unsigned int)time(NULL));
    cout << 1000000 << endl;
    rep(i,1000000) cout << rand() << endl;
    return 0;
  }
  
  int n;
   cin >> n;
  vector<int> vec(n);
  rep(i,n) cin >> vec[i];
  solve(vec);
  return 0;
}



Measured memory_bytes: 6700
#include<stdio.h>
int main()
{
  int a,b,c;
  scanf("%d %d %d", &a, &b, &c);
  if(a==b) printf("%d\n",c);
  else if(c==b) printf("%d\n",a);
  else printf("%d\n",b);
  return 0;
}

Measured memory_bytes: 128
#include <iostream>

using namespace std;

string A = "AKIHABARA";

int main() {
  string S;
  cin >> S;

  int i{}, j{}, n = S.size();
  while (i < n && j < (int)A.size()) {
    if (S[i] == A[j]) ++i, ++j;
    else if (A[j] == 'A') ++j;
    else break;
  }

  cout << (i == n && j > 7 ? "YES" : "NO") << endl;
}


Measured memory_bytes: 3620
#include<iostream>
using namespace std;
int main(){
    int H,W;
    while(1){
        cin >> H >> W;
        if(H == 0 && W == 0)break;
        for(int i = 0; i < H; i++ ){
            for(int j = 0; j < W; j++ ){
                if(i==0 || i==H-1 ||j==0 || j==W-1){
                    cout << "#";
                }else{
                    cout <<".";
                }
            }cout << endl;
        }
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 3028
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = in.nextInt();
		}
		
		long stool = 0;
		int max = a[0];
		for (int i = 0; i < n; i++) {
			max = Math.max(a[i], max);
			stool += max - a[i];
		}
		
		System.out.println(stool);
		
		in.close();
	}
}


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

int w,h,ans;

struct Ling{
	int a[21][21];
	int sx,sy,gx,gy,cost;
};

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


Ling go(Ling ling,int d){
	ling.cost++;
	if(ling.sx+dx[d]<0 || ling.sy+dy[d]<0 || ling.sx+dx[d]>=w || ling.sy+dy[d]>=h){
		ling.sx=-1;
		return ling;
	}
	if(ling.a[ling.sy+dy[d]][ling.sx+dx[d]]==1){
		ling.sx=-1;
		return ling;
	}

	while(ling.a[ling.sy][ling.sx]==0){
		ling.sy+=dy[d];
		ling.sx+=dx[d];
		if(ling.sx<0 || ling.sy<0 || ling.sx>=w || ling.sy>=h){
			ling.sx=-1;
			return ling;
		}
	}
	if(ling.a[ling.sy][ling.sx]==3)
		return ling;

	ling.a[ling.sy][ling.sx]=0;
	ling.sy-=dy[d];
	ling.sx-=dx[d];
	return ling;
}



void dfs(Ling ling){
	if(ling.cost>=10 || (ans>0 && ling.cost>ans))
		return;

	for(int d=0;d<4;d++){
		Ling nextling=go(ling,d);
		if(nextling.a[nextling.sy][nextling.sx]==3){
			if(ans==-1)
				ans=nextling.cost;
			else ans=min(nextling.cost,ans);
			continue;
		}
		else if(nextling.sx==-1)
			continue;

		dfs(nextling);
	}
}

void solve(){
	ans=-1;
	Ling ling;
	ling.cost=0;
	for(int y=0;y<h;y++){
		for(int x=0;x<w;x++){
			cin>>ling.a[y][x];
			if(ling.a[y][x]==2){
				ling.sx=x;
				ling.sy=y;
				ling.a[y][x]=0;
			}
			if(ling.a[y][x]==3){
				ling.gx=x;
				ling.gy=y;
			}
		}
	}
	dfs(ling);
	cout<<ans<<"\n";
}


int main(){
	cin>>w>>h;
	while(w!=0){
		solve();
		cin>>w>>h;
	}
	return 0;
}

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

using namespace std;

#define int long long
#define FOR(i, j, k) for(int i = j; i < k; ++i)
#define rep(i, j) FOR(i, 0, j)
#define INF 1e9
#define LINF 1e18

typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> Pi;
typedef pair<P, P> PP;

const int MOD = 1e9 + 7;
const int dy[]={0, 0, 1, -1};
const int dx[]={1, -1, 0, 0};

template <class T> void chmin(T& a, const T& b) { a = min(a, b); }
template <class T> void chmax(T& a, const T& b) { a = max(a, b); }

int N, M;
int p[100000];

//Union-Find木

int par[100000];     //親
int Rank[100000];    //木の深さ

void init(int n) {
    for(int i = 0; i < n; ++i) {
        par[i] = i;
        Rank[i] = 0;
    }
}

int find(int x) {
    return (par[x] == x) ? x : par[x] = find(par[x]);
}

void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if(x == y) return;

    if(Rank[x] < Rank[y]) par[x] = y;
    else {
        par[y] = x;
        if(Rank[x] == Rank[y]) ++Rank[x];
    }
}

bool same(int x, int y) {
    return find(x) == find(y);
}

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

    cin >> N >> M;
    rep(i, N) cin >> p[i];
    init(N);
    rep(i, M) {
        int x, y;
        cin >> x >> y;
        unite(x - 1, y - 1);
    }
    int res = 0;
    rep(i, N) {
        if(p[i] - 1 == i) ++res;
        else if(same(p[i] - 1, i)) ++res;
    }
    cout << res << endl;
    return 0;
}

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

int main(){
  double a[2];
  int m[4][2]={};
  while(cin >>a[0]>>a[1]){
    for(int i=0;i<2;i++){
      if(a[i]>=1.1)m[0][i]++;
      else if(a[i]>=0.6)m[1][i]++;
      else if(a[i]>=0.2)m[2][i]++;
      else m[3][i]++;
    }
  }
  for(int i=0;i<4;i++){
    for(int j=0;j<2;j++){
      cout << m[i][j];
      if(j==0)cout << " ";
      else cout << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 1224
#include<cstdio>
int main(){
    char s[5];
    scanf("%s",s);
    bool yymm=((s[2]=='0'&&s[3]!='0')||(s[2]=='1'&&s[3]<='2'));
    bool mmyy=((s[0]=='0'&&s[1]!='0')||(s[0]=='1'&&s[1]<='2'));
    if(yymm){
        if(mmyy)printf("AMBIGUOUS\n");
        else printf("YYMM\n");
    }else{
        if(mmyy)printf("MMYY\n");
        else printf("NA\n");
    }
    return 0;
}

Measured memory_bytes: 128
//agc025_a.cpp
//Sat Nov 10 16:23:33 2018

#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#define INTINF 2147483647
#define LLINF 9223372036854775807
using namespace std;
using ll=long long;
typedef pair<int,int> P;

int calcdigit(int a, int b){
	int temp1 = 0;
	while (a>0){
		temp1 += a%10;
		a = (a-a%10)/10;
	}
	while (b>0){
		temp1 += b%10;
		b = (b-b%10)/10;
	}
	return temp1;
}

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

	int a = 1;
	int b = n-1;
	int ans = INTINF;
	while (a<=n/2){
		int temp = calcdigit(a,b);
//		cout << a << " " << b << " " << temp << " " << ans << endl;
		if (temp < ans){
			ans = temp;
		}
		a++;
		b--;
	}

	cout << ans << endl;

}

Measured memory_bytes: 256
length = gets.to_i
arr = gets.split.map(&:to_i)

def bubble_sort(length, arr)
  count = 0
  for i in 0..(length - 2) do
    for j in 0..(length - i -2) do
      if arr[length - j -1] < arr[length - j - 2]
        arr[length - j -1], arr[length - j -2] = arr[length - j -2], arr[length - j -1]
        count += 1
      end
    end
  end
  [arr, count]
end

sorted_arr, count = bubble_sort(length, arr)

puts sorted_arr.join(' ')
puts count


Measured memory_bytes: 6876
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringBuilder s = new StringBuilder(sc.next());
		int answer = 0;

		for (int i = 1; i < s.length(); i++) {
			if (s.charAt(i) == s.charAt(i - 1)) {
				if (s.charAt(i) == '0') {
					s.setCharAt(i, '1');
				} else {
					s.setCharAt(i, '0');
				}
				answer++;
			}
		}
		System.out.println(answer);
	}
}


Measured memory_bytes: 27496
list = []
alphabet=dict.fromkeys("abcdefghijklmnopqrstuvwxyz",0)

while True:
    try:
        word = input()
        word=word.lower()
        list.append(word)
    except:
        break

#print(list)

list.sort()
#print(list)
s = "".join(list)
for i in alphabet:
    count_num=s.count(i)
    print(f"{i} : {count_num}")


Measured memory_bytes: 5572
// https://atcoder.jp/contests/abc129/tasks/abc129_d

#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <tuple>
#include <vector>
using namespace std;

typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
#define INF (1e9)
#define MOD (1000000007)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOREACH(x, a) for (auto &(x) : (a))
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
// int gcd(long a, long b) { return b ? gcd(b, a % b) : a; }
// int lcm(long a, long b) { return a * b / gcd(a, b); }

string s[2001];
int numh[2001][2001], numw[2001][2001];
int h, w;

// 縦方向に連続する空白を探す
int seqh(int _h, int _w) {
    if (s[_h][_w] == '#') {
        return 0;
    }
    if (numh[_h][_w] > 0) {
        return numh[_h][_w];
    }
    //上方向に空白を探す
    int posTop = _h, posBottom = _h;
    while (posTop >= 0 && s[posTop][_w] == '.') {
        posTop--;
    }
    posTop++;
    // 下方向に空白を探す
    while (posBottom <= h - 1 && s[posBottom][_w] == '.') {
        posBottom++;
    }
    posBottom--;
    int ans = posBottom - posTop + 1;
    for (int i = posTop; i <= posBottom; i++) {
        numh[i][_w] = ans;
    }
    return ans;
}

// 横方向に連続する空白を探す
int seqw(int _h, int _w) {
    if (s[_h][_w] == '#') {
        return 0;
    }
    if (numw[_h][_w] > 0) {
        return numw[_h][_w];
    }
    // 左方向に空白を探す
    int posLeft = _w, posRight = _w;
    while (posLeft >= 0 && s[_h][posLeft] == '.') {
        posLeft--;
    }
    posLeft++;
    // 右方向に空白を探す
    while (posRight < w && s[_h][posRight] == '.') {
        posRight++;
    }
    posRight--;
    int ans = posRight - posLeft + 1;
    for (int i = posLeft; i <= posRight; i++) {
        numw[_h][i] = ans;
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int ans = 0;
    cin >> h >> w;
    for (int i = 0; i < h; i++) {
        cin >> s[i];
    }

    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            // 縦横の交点は重複してカウントしないため-1
            ans = max(ans, seqh(i, j) + seqw(i, j) - 1);
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 35840
#include <bits/stdc++.h>
#define rep(i, n) for(int i= 0; i < (n); i++)
using ll= long long int;
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; }
ll mod= 1e9 + 7;

ll d[3]={3,5,7};
int ans=0;

bool check(ll g){
  bool e[3]={0,0,0};
  string k=to_string(g);
  int p=k.size();
  rep(r,p){
    if(k[r]=='3')e[0]=1;
    if(k[r]=='5')e[1]=1;
    if(k[r]=='7')e[2]=1;
  }
  if(e[0]==1 && e[1]==1 && e[2]==1){return 1;}else{return 0;}
}

void f(ll g,ll q){
  if(g>q)return;
  if(check(g))ans++;
  rep(ii,3){
    f(g*10+d[ii],q);
  }
}

int main(){
  ll x;
  cin >> x;
    f(0,x);
  cout << ans << endl;
}

Measured memory_bytes: 3740
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
struct bellford
{
    const ll INF=LLONG_MAX;
    struct edge {int u, v; ll w;};
    int nv, ne;
    vector<ll> d;
    vector<int> p;
    vector<edge> E;
 
    bellford(int nv, int ne) : nv(nv), ne(ne)
    {
        d.resize(nv, INF);
        p.resize(nv,-1);
    }
 
    void relax(int u, int v, ll w)
    {
        if(d[u]!=INF && d[v]>d[u]+w)
        {
            d[v]=d[u]+w;
            p[v]=u;
        }
    }
 
    bool get(int s)
    {
        d[s]=0; 
        for(int i=0; i<nv; i++)
            for(auto &e : E)
                relax(e.u, e.v, e.w);
 
        vector<bool> path(nv, false);
        path[nv-1]=true;
        int v=p[nv-1];
        while(v!=-1 && !path[v])
        {
            path[v]=true;
            v=p[v];
        }
        if(v!=-1) return false;
        return true;
    }
};
 
 
int main()
{
    int N, M;
    scanf("%d%d", &N, &M);
    bellford g(N, M);
    for(int i=0; i<M; i++)
    {
        int a, b;
        ll c;
        scanf("%d%d%lld", &a, &b, &c);
        g.E.push_back({a-1, b-1, -c});
    }
    if(g.get(0)) printf("%lld\n", -g.d[N-1]);
    else printf("inf\n");
    return 0;
}

Measured memory_bytes: 3852
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1050;

int a[maxn];

int main(){
     int n, m; cin >> n >> m;
     int sum = 0;
     for(int i = 0; i < n; i++){
          cin >> a[i];
          sum += a[i];
     }
     int ans = 0;
     int reminder = sum % (4*m);
     for(int i = 0; i < n; i++)
          if((reminder == 0 && a[i] < sum/4/m) || (reminder && a[i] <= sum/4/m)) ans++;
     if(n-ans >= m) puts("Yes");
     else puts("No");
}


Measured memory_bytes: 256
/*
   THE DARK NIGHT RISES
I LOVE YOU 72 AND WILL FOREVER DO SO
Patience, Persistence, Perseverance, Passion, Purpose
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
const int N = 2e5 + 20 ;
#define F first
#define S second
# define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
#define mk make_pair
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i,a,b) for(ll i=a;i<b;i++)
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define sz(x)       (int)x.size()
const long long int mod=1e9 + 7;
const long double EPS=1e-12;
#define mem( a, val ) memset(a, val, sizeof( a ) )
#define deci( x ) cout<<fixed<<setprecision( x );
#define bitcount( x ) __builtin_popcountll( x )

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

int solve()
{
  ll n , a ,b , c;;
  cin >> n >> a >> b >> c ;
  ll dp[n+2][3] ={0} ;
  dp[0][0] = a , dp[0][1] = b ,dp[0][2] = c ;
  rep(i,1,n)
  {
    cin >> a >> b >> c ;
    dp[i][0] = max(dp[i-1][1],dp[i-1][2]) +a ;
    dp[i][1] = max(dp[i-1][0],dp[i-1][2]) +b ;
    dp[i][2] = max(dp[i-1][1],dp[i-1][0]) +c ;
  }
  cout << max({dp[n-1][0],dp[n-1][1],dp[n-1][2]});
}
int main()
{
  fast;
  ll t;
  t=1;
  //cin>>t;
  while(t--)
  {
    solve();
  }

  return 0;
}
// Patience, Persistence, Perseverance, Passion, Purpose
// I LOVE YOU 72 AND WILL FOREVER DO SO.

Measured memory_bytes: 2560
#include <iostream>

using namespace std;

int main() {
	
	int score[10];

	while (cin >> score[0]) {

		int sum = score[0];

		for (int i = 1; i < 10; i++) {

			cin >> score[i];
			sum += score[i];

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

}







Measured memory_bytes: 3124
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, x, ans = 0, i;
    vector <int> v;
    
    scanf("%d %d", &n, &x);
    
    for (i = 0; i < n; i++) {
        int a;
        
        scanf("%d", &a);
        
        v.push_back(a);
    }
    
    sort(v.begin(), v.end());
    
    for (i = 0; i < n; i++) {
        if (v[i] <= x) {
            x -= v[i];
            ans++;
        } else {
            break;
        }
    }
    
    if (i == n && x > 0) ans--;
    
    printf("%d\n", ans);
    
    return 0;
}


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

int main() {
  string s;
  cin >> s;
  if(s == "SUN") cout << 7;
  else if(s == "MON") cout << 6;
  else if(s == "TUE") cout << 5;
  else if(s == "WED") cout << 4;
  else if(s == "THU") cout << 3;
  else if(s == "FRI") cout << 2;
  else cout << 1;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define mset(a, b) memset(a, b, sizeof(a))
#define mcpy(a, b) memcpy(a, b, sizeof(a))
#define rg register
#define lc (rt << 1)
#define rc (rt << 1) | 1
using namespace std;
typedef long long LL;
const int MAXN = 200005;

template <typename T> inline void read(T &AKNOI) {
    T x = 0, flag = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') flag = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    AKNOI = flag * x;
}

template <typename T> inline void cmin(T &x, T y) {
	if (x > y) x = y;
}

int n, m, s[MAXN], sum;
vector<int> vec[MAXN];

struct SegmentTree {
	int mn[MAXN << 2], tag[MAXN << 2];
	
	inline void pushup(int rt) {
		mn[rt] = min(mn[lc], mn[rc]);
	}
	
	inline void puttag(int rt, int tg) {
		mn[rt] += tg;
		tag[rt] += tg;
	}
	
	inline void pushdown(int rt) {
		if (!tag[rt]) return;
		puttag(lc, tag[rt]);
		puttag(rc, tag[rt]);
		tag[rt] = 0;
	}
	
	void Modify(int rt, int b, int e, int p, int v) {
		if (b == e) {
			cmin(mn[rt], v);
			return;
		}
		int mid = (b + e) >> 1;
		pushdown(rt);
		if (p <= mid) Modify(lc, b, mid, p, v);
		else Modify(rc, mid + 1, e, p, v);
		pushup(rt);
	}
	
	void Update(int rt, int b, int e, int l, int r, int v) {
		if (l <= b && e <= r) {
			puttag(rt, v);
			return;
		}
		int mid = (b + e) >> 1;
		pushdown(rt);
		if (l <= mid) Update(lc, b, mid, l, r, v);
		if (r > mid) Update(rc, mid + 1, e, l, r, v);
		pushup(rt);
	}
	
	int Query(int rt, int b, int e, int l, int r) {
		if (l <= b && e <= r) return mn[rt];
		int mid = (b + e) >> 1;
		pushdown(rt);
		if (r <= mid) return Query(lc, b, mid, l, r);
		if (l > mid) return Query(rc, mid + 1, e, l, r);
		return min( Query(lc, b, mid, l, r), Query(rc, mid + 1, e, l, r) );
	}
} tr;

void init() {
	read(n);
	for (int i = 1; i <= n; ++i) {
		read(s[i]);
		sum += (s[i] == 0);
	}
	read(m);
	for (int i = 1, l, r; i <= m; ++i) {
		read(l); read(r);
		vec[l].push_back(r);
	}
}

void solve() {
	mset(tr.mn, 0x3f);
	tr.Modify(1, 0, n, 0, 0);
	for (int i = 1; i <= n; ++i) {
		for (auto j : vec[i]) {
			int x = tr.Query(1, 0, n, 0, j);
			tr.Modify(1, 0, n, j, x);
		}
		tr.Update(1, 0, n, 0, i - 1, s[i]? 1 : -1);
	}
	printf("%d\n", tr.Query(1, 0, n, 0, n) + sum);
}

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


Measured memory_bytes: 15872
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define endl "\n"
const int MOD=1e9+7;
#ifndef HOME
#define cerr if(0)cerr
#endif
const int MaxN = 1e5+5;
int dp[MaxN][3];
int a[MaxN][3];
int n;
int solve(int i,int type){
    if(i==n){
        return 0;
    }
    int &ans = dp[i][type];
    if(ans!=-1){
        return ans;
    }
    int res = 0;
    if(i==0){
        res = max(res,a[i][0]+solve(i+1,1));
        res = max(res,a[i][0]+solve(i+1,2));
        res = max(res,a[i][1]+solve(i+1,2));
        res = max(res,a[i][1]+solve(i+1,0));
        res = max(res,a[i][2]+solve(i+1,1));
        res = max(res,a[i][2]+solve(i+1,0));
    }else{
        for(int j=0;j<3;j++){
            if(type!=j){
                res = max(res,a[i][type]+solve(i+1,j));
            }
        }
    }
    return ans = res;
}
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i][0]>>a[i][1]>>a[i][2];
    }
    memset(dp,-1,sizeof(dp));
    cout<<solve(0,0);
    return 0;
    
}



Measured memory_bytes: 12800