akhauriyash/Code-Regression huggingface dataset:
#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

const int MOD = 1000000007, INF = 1111111111;
using namespace std;
using lint = long long;

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
	for (int i = 0; i < vec.size(); i++) {
		os << vec[i] << (i + 1 == vec.size() ? "" : " ");
	}
	return os;
}

#ifdef _DEBUG
template <class Head>
void dump(const char* str, Head &&h) { cerr << str << " = " << h << "\n"; };
template <class Head, class... Tail>
void dump(const char* str, Head &&h, Tail &&... t) {
	while (*str != ',') cerr << *str++; cerr << " = " << h << "\n";
	dump(str + 1, t...);
}
#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)
#else 
#define DMP(x) ((void)0)
#endif

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	string S;
	cin >> S;
	
	S[3] = '8';
	cout << S << "\n";

	return 0;
}

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

using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;

const ll mod = 1e9 + 7;

vector<ll> dx = {1, -1, 0, 0};
vector<ll> dy = {0, 0, 1, -1};

vector<string> g;

int main() {
    
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    
    ll n;
    cin >> n;
    bool f = 1;
    ll num = 0;
    for (int i = 1; i <= 1e5; ++i)
    {
        if (n == ((i + 1) * i) / 2)
        {
            num = i;
            f = 0;
            break;
        }
    }
    
    if (f)
    {
        cout << "No" << endl;
        return 0;
    }
    else
    {
        cout << "Yes" << endl;
        cout << num + 1 << endl;
    }
    
    vector<vector<ll>> nn(num + 1, vector<ll>(num + 1, -1));
    ll tmp = 1;
    for (int i = 1; i <= num; ++i)
    {
        for (int j = 0; j < i; ++j)
        {
            nn[i][j] = tmp;
            tmp++;
        }
    }
    
    for (int i = 1; i <= num; ++i)
    {
        cout << num << " ";
        for (int j = 1; j < i; ++j)
        {
            cout << nn[i][j - 1] << " ";
        }
        for (int j = i; j <= num; ++j)
        {
            cout << nn[j][i - 1];
            if (j == num)
            {
                cout << endl;
            }
            else
            {
                cout << " ";
            }
        }
    }
    ll cur = 0;
    cout << num << " ";
    for (int i = 1; i <= num; ++i)
    {
        cur += i;
        cout << cur;
        if (i == num)
        {
            cout << endl;
        }
        else
        {
            cout << " ";
        }
    }
    
    return 0;
}

Measured memory_bytes: 2944
import java.util.*;
import java.io.*;

public class Main {


    public Main(FastScanner in, PrintWriter out, int test) {
        int p = in.nextInt();
        out.println((p + 999) / 1000 * 1000 - p);
    }

    public static void main(String[] args) {
        PrintWriter out = new PrintWriter(System.out);
        // Scanner in = new Scanner(
                // new BufferedReader(new InputStreamReader(System.in)));
        FastScanner in = new FastScanner(System.in);

        // int T = in.nextInt();
        for (int t = 1; t <= 1; t++) {
            Main sol = new Main(in, out, t);
        }

        out.close();
    }
}


class FastScanner{
    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;

    public FastScanner(InputStream stream)
    {
        this.stream = stream;
    }

    int read()
    {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars){
            curChar = 0;
            try{
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }

    boolean isSpaceChar(int c)
    {
        return c==' '||c=='\n'||c=='\r'||c=='\t'||c==-1;
    }

    boolean isEndline(int c)
    {
        return c=='\n'||c=='\r'||c==-1;
    }

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

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

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

    String next(){
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do{
            res.appendCodePoint(c);
            c = read();
        }while(!isSpaceChar(c));
        return res.toString();
    }

    String nextLine(){
        int c = read();
        while (isEndline(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do{
            res.appendCodePoint(c);
            c = read();
        }while(!isEndline(c));
        return res.toString();
    }
}

Measured memory_bytes: 32276
import Control.Applicative
import Control.Monad
import Control.Monad.ST
import qualified Data.ByteString as BS
import Data.Functor
import Data.Function
import Data.Monoid
import Data.Maybe
import Data.List
import qualified Data.Foldable as Foldable
import qualified Data.Set as Set
--import qualified Data.Sequence as Sequence
import Data.List.Split
import Data.Bits
import Data.Char
import Data.Ix
import Data.Ratio
import Data.Ord
import Data.Tuple
--import Data.Array
--import Data.Array.Unboxed
import Data.Array.IArray
import Data.Array.MArray
import Data.Array.IO
import Data.Array.ST
import Data.IORef
import Data.STRef
-- import System.IO.Unsafe

-- templete
readInt = read :: String -> Int
readInteger = read :: String -> Integer
readDouble = read :: String -> Double
getInt = readLn :: IO Int
getInts = map readInt . words <$> getLine
getInteger = readLn :: IO Integer
getIntegers = map readInteger . words <$> getLine
getDouble = readLn :: IO Double
getDoubles = map readDouble . words <$> getLine
sjoin :: (Show a) => [a] -> String
sjoin = unwords . map show
cond :: a -> a -> Bool -> a
cond t f c = if c then t else f
apply2 :: (a -> a -> b) -> [a] -> b
apply2 f [x,y] = f x y
apply3 :: (a -> a -> a -> b) -> [a] -> b
apply3 f [x,y,z] = f x y z
apply4 :: (a -> a -> a -> a -> b) -> [a] -> b
apply4 f [x,y,z,w] = f x y z w
fnTuple :: (a -> b, a -> c) -> a -> (b, c)
fnTuple (f,g) a = (f a, g a)
replace :: (Eq a) => a -> a -> [a] -> [a]
replace x y = map (\z -> if z==x then y else z)
binMap :: (a -> a -> b) -> [a] -> [b]
binMap f (x:xs@(y:_)) = f x y : binMap f xs
binMap _ _ = []
splitRec :: Int -> [a] -> [[a]]
splitRec _ [] = []
splitRec n xs = let (y,ys) = splitAt n xs in y : splitRec n ys
infixl 7 `divCeil`
divCeil :: Integral a => a -> a -> a
x `divCeil` y = (x+y-1) `div` y
coverC :: Ord a => (a, a) -> a -> Bool
coverC (l,r) x = l<=x && x<=r
coverH :: Ord a => (a, a) -> a -> Bool
coverH (l,r) x = l<=x && x<r
-- templete

det3 (a,b,c) (p,q,r) (x,y,z) = a*q*z + b*r*x + c*p*y - a*r*y - b*p*z - c*q*x

f e b1 b2 b3
  | d0 == 0 = False
  | r>=1 && 0<=c1 && c1<=r && 0<=c2 && c2<=r && 0<=c3 && c3<=r = False
  | otherwise = True
  where
    d0 = det3 b1 b2 b3
    c1 = det3 e b2 b3 / d0
    c2 = det3 b1 e b3 / d0
    c3 = det3 b1 b2 e / d0
    r = c1 + c2 + c3

main = do
    uaz <- getIntegers
    enemy <- getIntegers
    barrier <- replicateM 3 getIntegers
    let m_enemy = apply3 (,,) . map (%1) . zipWith subtract uaz $ enemy
    let m_barrier = map (apply3 (,,) . map (%1) . zipWith subtract uaz) barrier
    putStrLn $ cond "HIT" "MISS" $ apply3 (f m_enemy) m_barrier


Measured memory_bytes: 3820
#include<iostream>
#include<fstream>
#include<math.h>
#include<vector>
#include<algorithm>
#define _cin ios_base::sync_with_stdio(0);  cin.tie(0);
#define ll long long 
#define mod 998244353
using namespace std;



int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
    #endif
    _cin;

    long long n;
    cin>>n;
    vector<int> arr;
    char alpha[26];
    
    for(int i=0;i<26;i++){
        alpha[i] = i+'a';
    }
    if(n==0)arr.push_back(0);
    while(n!=0){
        n-=1;
        arr.push_back(n%26);
        n=n/26;
    }
    int count = 0;
    std::vector<int>::reverse_iterator i;
    for( i=arr.rbegin(); i!=arr.rend(); ++i){
        if(count != arr.size()-1)cout<< alpha[*i];
        else cout<<alpha[*i];
        count++;
    }

}

Measured memory_bytes: 3124
#include <bits/stdc++.h>
using namespace std; 
int dp[1<<9][10][200];

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

  while(q--){
    int a[9],b[9];
    for(int i=0;i<9;i++)cin>>a[i];
    for(int i=0;i<9;i++)cin>>b[i];

    memset(dp,0,sizeof(dp));
    dp[0][0][0]=1;

    for(int i=0;i<(1<<9);i++)
      for(int j=0;j<9;j++){
	if(__builtin_popcount(i)!=j) continue;
	for(int k=0;k<9;k++){
	  if((i&(1<<k)))continue;
	  for(int s=0;s<180;s++){
	    if(a[j]<b[k])dp[i|(1<<k)][j+1][s]+=dp[i][j][s];
	    else dp[i|(1<<k)][j+1][s+a[j]+b[k]]+=dp[i][j][s];
	  }
	}
      }

    double sum=1,ans=0;
    for(int i=1;i<=9;i++) sum*=i;
    for(int i=86;i<180;i++) ans+=dp[(1<<9)-1][9][i];
    ans=ans/sum;
    printf("%lf %lf\n",ans,1-ans);
  }
  return 0;
}

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

ll maxll(int x, int y)
{
    if (x > y)
        return ll(x);
    else
        return ll(y);
}
ll minll(ll x, ll y)
{
    if (x > y)
        return ll(y);
    else
        return ll(x);
}

int main()
{
    int n, m, m1;
    cin >> n >> m;
    m1 = m;
    vector<pair<int, int>> p(n);
    vector<int> sum(n, 0);

    for (int i = 0; i < n; i++)
    {
        cin >> p[i].first >> p[i].second;
    }
    sort(p.begin(), p.end());
    for (auto x : p)
    {
        //printf("%d円が%d本\n", x.first, x.second);
    }

    ll ans = 0;
    for (int i = 0; i < n; i++)
    {
        ans += minll(ll(p[i].first) * ll(p[i].second), ll(m) * ll(p[i].first));
        //printf("買った本数 = %d,金額 = %lld\n", min(m, p[i].first), ans);
        m -= minll(p[i].second, m);
    }
    cout << ans << endl;
}

Measured memory_bytes: 1408
package main

import "fmt"

func main() {
	var a, b, c int
	fmt.Scan(&a, &b, &c)

	mod := make(map[int]bool)
	for i := 0; ; i++ {
		sum := a * i
		sum %= b
		if sum == c {
			fmt.Println("YES")
			return
		} else if mod[sum] {
			fmt.Println("NO")
			return
		}
		mod[sum] = true
	}
}


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

int main() {
  int n;
  long long dp[50] = {0};
  for (int i = 0; i <= 30; i++) {
    if (i == 0) {
      dp[i] = 1;
    }
    else if (i == 1) {
      dp[i] = dp[i-1];
    }
    else if (i == 2) {
      dp[i] = dp[i-2] + dp[i-1];
    }
    else {
      dp[i] = dp[i-3] + dp[i-2] + dp[i-1];
    }
  }
  while (cin >> n && n > 0) {
    cout << (dp[n] + 3650 - 1)/3650 << endl;
  }
  return 0;
}


Measured memory_bytes: 2984
#include <iostream>
#include <map>
#include <cmath>

using ll = long long;

ll n;

std::map<ll, ll> mapa;
long heights[2000001];

int main() {
    std::cin >> n;
    ll solutions = 0;
    for (ll i = 0, tmp; i < n; ++i) {
        std::cin >> tmp;
        mapa[tmp + i] += 1;
        heights[i] = tmp;
    }
    for (ll i = 0; i < n; ++i) {
        if ((i - heights[i]) >= 0)
        solutions += mapa[i - heights[i]];
    }
    std::cout << solutions;
    return 0;
}

Measured memory_bytes: 18792
import java.io.*;
import java.util.*;

public class Main{
	
	public static void main(String[] args) throws Exception{
		pw=new PrintWriter(System.out);
		sc = new MScanner(System.in);
		long a=sc.nextLong(),b=sc.nextLong(),n=sc.nextLong();
		pw.println((a*Math.min(b-1, n))/b);
		
		pw.flush();
	}
	static PrintWriter pw;
	static MScanner  sc;
	static class MScanner {
		StringTokenizer st;
		BufferedReader br;
		public MScanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}
 
		public MScanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}
 
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public int[] intArr(int n) throws IOException {
	        int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        return in;
		}
		public long[] longArr(int n) throws IOException {
	        long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        return in;
		}
		public int[] intSortedArr(int n) throws IOException {
	        int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        shuffle(in);
	        Arrays.sort(in);
	        return in;
		}
		public long[] longSortedArr(int n) throws IOException {
	        long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        shuffle(in);
	        Arrays.sort(in);
	        return in;
		}
		public Integer[] IntegerArr(int n) throws IOException {
	        Integer[]in=new Integer[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        return in;
		}
		public Long[] LongArr(int n) throws IOException {
	        Long[]in=new Long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        return in;
		}
		public String nextLine() throws IOException {
			return br.readLine();
		}
 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
 
		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
 
		public char nextChar() throws IOException {
			return next().charAt(0);
		}
 
		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
 
		public boolean ready() throws IOException {
			return br.ready();
		}
 
		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}
	static void shuffle(int[]in) {
		for(int i=0;i<in.length;i++) {
			int idx=(int)(Math.random()*in.length);
			int tmp=in[i];
			in[i]=in[idx];
			in[idx]=tmp;
		}
	}
	static void shuffle(long[]in) {
		for(int i=0;i<in.length;i++) {
			int idx=(int)(Math.random()*in.length);
			long tmp=in[i];
			in[i]=in[idx];
			in[idx]=tmp;
		}
	}
}

Measured memory_bytes: 32616
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    boolean result = true;
    char[] cs = sc.next().toCharArray();
    for(int i = 0; i < cs.length; i++)
      if(cs[i] == (i % 2 == 0 ? 'L' : 'R'))
        result = false;
    System.out.println(result ? "Yes" : "No");
  }
}

Measured memory_bytes: 25172
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
typedef long long ll;
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 NMAX = 100010;
vector<vector<ll>> dp(NMAX, vector<ll>(3, 0));
vector<vector<int>> h(NMAX, vector<int>(3, -1));
int main()
{
    int N;
    cin >> N;

    REP(i, N) cin>>h[i][0]>>h[i][1]>>h[i][2];

    REP2(i,1,N+1){
        REP(j,3){
            REP(k,3){
                if(j==k) continue;
                chmax(dp[i][j], dp[i-1][k]+h[i-1][j]);
            }
        }
    }

    ll res = 0;
    REP(i,3) chmax(res, dp[N][i]);

    cout << res << endl;

    return 0;
}

Measured memory_bytes: 11136
/* In the name of Allah */

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define LL_INF 1LL << 62
#define INF 1 << 30
#define SetBit(x, k) (x |= (1LL << k))
#define ClearBit(x, k) (x &= ~(1LL << k))
#define CheckBit(x, k) (x & (1LL << k))
#define mod 1000000007

int n, w;

ll x[105], y[105];
ll dp[102][100005];

ll solve(int pos, int val){
  if(val < 0) return LL_INF;
  if(pos >= n){
    if(val == 0) return 0;
    return LL_INF;
  }

  if(dp[pos][val]!=-1) return dp[pos][val];

  ll res = LL_INF;
  res = min(res, solve(pos+1, val));
  res = min(res, x[pos]+solve(pos+1, val-y[pos]));

  return dp[pos][val] = res;
}

int main()
{
  memset(dp, -1, sizeof dp);
  cin >> n >> w;
  for(int i = 0; i < n; i++)
    cin >> x[i] >> y[i];

  int mx = 0;
  for(int i = 1; i <= 100000; i++){
    if(solve(0, i)<=w) mx = i;
  }

  cout << mx << "\n";

  return 0;
}

Measured memory_bytes: 83264
#include <bits/stdc++.h>
#define rt "\n"
#define sp " "
#define test(n) cout << "test" << n << endl;
#define fixsp(n) fixed << setprecision(n)
#define defsp(n) defaultfloat << setprecision(n)
#define kyopro ios::sync_with_stdio(false);cin.tie(NULL)
#define MOD 1000000007
#define iikae auto&
#define vector3D(K, N, M, DP) vector<vector<vector<ll>>> DP(K, vector<vector<ll>>(N, vector<ll>(M)));
#define vector4D(K, N, M, O, DP) vector<vector<vector<vector<ll>>>> DP(K, vector<vector<vector<ll>>>(N, vector<vector<ll>>(M, vector<ll>(O))));
#define zenbu(a) a.begin(), a.end()
#define rzenbu(a) a.rbegin(), a.rend()
#define rep(i, s, N) for(ll i{s}; i < N; i++)
#define rem(i, N, s) for(ll i{N}; i > s; i--)
using namespace std;using ll = long long;using ld = long double;using P = pair<ll,ll>;/* 最大公約数 */template<typename T> T gcd(T a, T b){return b != 0 ? gcd(b, a % b) : a;}/* UnionFind */template<typename T> struct UnionFind{vector<T> par;UnionFind(T n) : par(n, -1){}void init(T n){par.assign(n, -1);}T root(T x){if (par[x] < 0) return x;else return par[x] = root(par[x]);}bool issame(T x, T y){return root(x) == root(y);}bool merge(T x, T 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)];}};/* コンビネーション */template<typename T> ll combpm(T N_, T C_) {const int NUM_=400001;static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];if (fact[0]==0) {inv[1]=fact[0]=factr[0]=1;for (int i=2;i<=NUM_;++i) inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%MOD, factr[i]=factr[i-1]*inv[i]%MOD;}if(C_<0 || C_>N_) return 0;return factr[C_]*fact[N_]%MOD*factr[N_-C_]%MOD;}
/* ここからコード開始 */

int main(){
  kyopro;
  ll N;
  cin >> N;
  ll ans{};
  cin >> ans;
  rep(i, 0, N-1){
    ll k;
    cin >> k;
    ans = gcd(ans, k);
  }
  cout << ans << rt;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto& (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define sar(a,n) cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl

using namespace std;

template<typename S,typename T>auto&operator<<(ostream&o,pair<S,T>p){return o<<"{"<<p.fi<<","<<p.se<<"}";}
template<typename T>auto&operator<<(ostream&o,set<T>s){for(auto&e:s)o<<e<<" ";return o;}
template<typename S,typename T,typename U>
auto&operator<<(ostream&o,priority_queue<S,T,U>q){while(!q.empty())o<<q.top()<<" ",q.pop();return o;}
template<typename K,typename T>auto&operator<<(ostream&o,map<K,T>&m){for(auto&e:m)o<<e<<" ";return o;}
template<typename T>auto&operator<<(ostream&o,vector<T>v){for(auto&e:v)o<<e<<" ";return o;}
void ashow(){cout<<endl;}template<typename T,typename...A>void ashow(T t,A...a){cout<<t<<" ";ashow(a...);}
template<typename S,typename T,typename U>
struct TRI{S fi;T se;U th;TRI(){}TRI(S f,T s,U t):fi(f),se(s),th(t){}};
template<typename S,typename T,typename U>
auto&operator<<(ostream&o,TRI<S,T,U>&t){return o<<"{"<<t.fi<<","<<t.se<<","<<t.th<<"}";}

typedef pair<int, int> P;
typedef pair<ll, ll> pll;
typedef TRI<int, int, int> tri;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<P> vp;
typedef vector<double> vd;
typedef vector<string> vs;

const int MAX_N = 100005;

ll dp[5005][5005];

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vp vec(n);
    rep(i,n){
        cin >> vec[i].fi >> vec[i].se;
    }
    sort(all(vec),[&](const P& p1, const P& p2){
        return p1.fi+p1.se < p2.fi+p2.se;
    });
    rep(i,n+1){
        rep(j,i+1){
            dp[i][j] = (1LL << 60);
        }
    }
    dp[0][0] = 0;
    rep(i,n){
        rep(j,i+1){
            if(dp[i][j] <= vec[i].fi){
                cmn(dp[i+1][j+1], dp[i][j]+vec[i].se);
            }
            cmn(dp[i+1][j], dp[i][j]);
        }
    }
    rrep(i,n+1){
        if(dp[n][i] != (1LL << 60)){
            cout << i << "\n";
            return 0;
        }
    }
    return 0;
}


Measured memory_bytes: 194048
// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,k,f[N];

struct edge { int v,nxt; } e[N];
int head[N];
inline void addEdge(int u,int v) {
    static int c=0;
    e[++c]=(edge){v,head[u]},head[u]=c;
}

int ans=0;
inline int dfs(int u,int dep) { int mxd=dep;
    for (re int i=head[u];i;i=e[i].nxt)
        mxd=max(mxd,dfs(e[i].v,dep+1));
    if (f[u]!=1&&mxd-dep+1==k) f[u]=1,++ans,mxd=0;
    return mxd;
}

int main() {
    n=read(),k=read();
    for (re int i=1;i<=n;++i) f[i]=read();
    for (re int i=2;i<=n;++i) addEdge(f[i],i);
    if (f[1]!=1) f[1]=1,++ans;
    dfs(1,0); printf("%d\n",ans);
    return 0;
}


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


int main(){
	int h, w, n;
	cin >> h >> w >> n;
	int ex = max(h, w);
	if (n % ex == 0 )cout << n / ex << endl;
	else cout << n /ex + 1 << endl;
	return 0;
}


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

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

using namespace std;

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

struct Stat{
	int x,y,dir,mem;
	Stat(){}
	Stat(int X,int Y,int D,int M):x(X),y(Y),dir(D),mem(M){}
};

void update(int &x,int &y,int dir,int r,int c){
	x=(x+dx[dir]+c)%c;
	y=(y+dy[dir]+r)%r;
}

int main(){
	int r,c; scanf("%d%d",&r,&c);
	char prog[20][21];
	rep(i,r) scanf("%s",prog[i]);

	bool end=false;
	bool visited[20][20][4][16]={};
	queue<Stat> qu; qu.push(Stat(0,0,0,0));
	while(!qu.empty()){
		Stat s=qu.front(); qu.pop();
		int x=s.x,y=s.y,dir=s.dir,mem=s.mem;

		if(visited[x][y][dir][mem]) continue;
		visited[x][y][dir][mem]=true;

		if(prog[y][x]=='@'){ end=true; break; }

		switch(prog[y][x]){
			case '<':
				dir=2;
				update(x,y,dir,r,c);
				qu.push(Stat(x,y,dir,mem));
				break;

			case '>':
				dir=0;
				update(x,y,dir,r,c);
				qu.push(Stat(x,y,dir,mem));
				break;

			case '^':
				dir=1;
				update(x,y,dir,r,c);
				qu.push(Stat(x,y,dir,mem));
				break;

			case 'v':
				dir=3;
				update(x,y,dir,r,c);
				qu.push(Stat(x,y,dir,mem));
				break;

			case '_':
				if(mem==0) dir=0;
				else       dir=2;
				update(x,y,dir,r,c);
				qu.push(Stat(x,y,dir,mem));
				break;

			case '|':
				if(mem==0) dir=3;
				else       dir=1;
				update(x,y,dir,r,c);
				qu.push(Stat(x,y,dir,mem));
				break;

			case '?':
				for(dir=0;dir<4;dir++){
					int xx=x,yy=y;
					update(xx,yy,dir,r,c);
					qu.push(Stat(xx,yy,dir,mem));
				}
				break;

			case '.':
				update(x,y,dir,r,c);
				qu.push(Stat(x,y,dir,mem));
				break;

			case '0': case '1': case '2': case '3': case '4':
			case '5': case '6': case '7': case '8': case '9':
				mem=prog[y][x]-'0';
				update(x,y,dir,r,c);
				qu.push(Stat(x,y,dir,mem));
				break;

			case '+':
				mem=(mem+1)%16;
				update(x,y,dir,r,c);
				qu.push(Stat(x,y,dir,mem));
				break;

			case '-':
				mem=(mem-1+16)%16;
				update(x,y,dir,r,c);
				qu.push(Stat(x,y,dir,mem));
				break;
		}
	}

	puts(end?"YES":"NO");

	return 0;
}

Measured memory_bytes: 0
#include<stdio.h>

int main(){
  int i;
  char s[20], A[6], B[8], C[6];
  
  scanf("%s", s);
  
  for (i = 0; i < 5; i++){
    A[i] = s[i];
  }
  A[5] = 0;
  for (i = 6; i < 13; i++){
    B[i-6] = s[i];
  }
  B[7] = 0;
  for (i = 14; i < 19; i++){
    C[i-14] = s[i];
  }
  C[5] = 0;
  
  printf("%s %s %s\n", A, B, C);
  
  return 0;
}

Measured memory_bytes: 128
/*  -*- coding: utf-8 -*-
 *
 * a.cc: A - Ice Tea Store
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

/* typedef */

typedef long long ll;

/* global variables */

/* subroutines */

/* main */

int main() {
  ll q, h, s, d, n;
  cin >> q >> h >> s >> d >> n;

  ll c2 = min(d, min(s * 2, min(h * 4, q * 8)));
  ll c1 = min(s, min(h * 2, q * 4));

  ll x = n / 2 * c2 + (n & 1) * c1;
  printf("%lld\n", x);

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define pa pair<int,int>
const int Maxn=100010;
const int inf=2147483647;
LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*f;
}
int n;
LL c,dis[Maxn],v[Maxn];
LL s1[Maxn],s2[Maxn],mx1[Maxn],mx2[Maxn];
int main()
{
	n=read(),c=read();
	s1[0]=s2[n+1]=0;
	for(int i=1;i<=n;i++)
	{
		dis[i]=read(),v[i]=read();
		s1[i]=s1[i-1]+v[i];
	}
	for(int i=n;i;i--)s2[i]=s2[i+1]+v[i];
	mx1[n+1]=0;
	for(int i=n;i;i--)mx1[i]=max(mx1[i+1],s2[i]+dis[i]);
	mx2[0]=0;
	for(int i=1;i<=n;i++)mx2[i]=max(mx2[i-1],s1[i]-dis[i]);
	LL ans=0;
	for(int i=1;i<=n;i++)
	{
		LL t=s1[i]-dis[i];
		ans=max(ans,t);
		ans=max(ans,t+mx1[i+1]-(dis[i]+c));
	}
	for(int i=n;i;i--)
	{
		LL t=s2[i]-(c-dis[i]);
		ans=max(ans,t);
		ans=max(ans,t+mx2[i-1]-(c-dis[i]));
	}
	printf("%lld",ans);
}


Measured memory_bytes: 4992
#include <algorithm>
#include <functional>
#include <cstdio>

using namespace std;

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

    int array[n];
    for (int i = 0; i < n; i++){
        scanf(" %d", &array[i]);
    }
    
    for (int i = n - 1; i >= 0; i--){
        if(i != 0){
            printf("%d ", array[i]);
        }
        else {
            printf("%d\n", array[i]);
        }
    }
    return 0;
}

Measured memory_bytes: 1024
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
using ld = long double;
template<typename T> using V = vector<T>;
template<typename T> using VV = vector<vector<T>>;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,a,n) for(ll i=a;i<(ll)(n);++i)
#define repr(i,a,n) for(ll i=n-1;(ll)a<=i;--i)
#define ENDL '\n'
typedef pair<int,int> Pi;
typedef pair<ll,ll> PL;
constexpr ll mod = 1000000007;
constexpr ll INF = 1000000099;
constexpr ll LINF = (ll)(1e18 +99);
const vector<ll> dx={-1,1,0,0},dy={0,0,-1,1};
template<typename T,typename U> inline bool chmin(T& t, const U& u){if(t>u){t=u;return 1;}return 0;}
template<typename T,typename U> inline bool chmax(T& t, const U& u){if(t<u){t=u;return 1;}return 0;}
template<typename T> inline T gcd(T a,T b){return b?gcd(b,a%b):a;}

template<typename T,typename Y> inline T mpow(T a, Y n) {
  T res = 1;
  for(;n;n>>=1) {
    if (n & 1) res = res * a;
    a = a * a;
  }
  return res;
}

template<typename T,typename Y>
ostream& operator<<(ostream& os,const pair<T,Y>& p){
   return os<<"{"<<p.fs<<","<<p.sc<<"}";
}
template<typename T> ostream& operator<<(ostream& os,const V<T>& v){
   os<<"{";
  for(auto e:v)os<<e<<",";
  return os<<"}";
}
template<typename ...Args>
void debug(Args&... args){
  for(auto const& x:{args...}){
    cerr<<x<<' ';
  }
  cerr<<ENDL;
}



signed main(){
  cin.tie(0);cerr.tie(0);ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(20);
  ll a,b,c,d,e;cin>>a>>b>>c>>d>>e;
  ll s=60*a+b,t=60*c+d;
  cout<<max(0ll,t-s-e)<<ENDL;
}
//! ( . _ . ) ! 
//CHECK overflow,vector_size,what to output?

Measured memory_bytes: 3620
from collections import defaultdict
import numpy as np
from scipy.sparse import bsr_matrix
from scipy.sparse.linalg import spsolve
def inpl(): return list(map(int, input().split()))

N = int(input())
A = np.array(inpl(), dtype=np.int64) * 2

data = np.ones(2*N, dtype=np.int64)
R = np.array([i//2 + i%2 for i in range(-1, 2*N-1)], dtype=np.int64)
C = np.array([N-1, 0] + [i//2 + i%2 for i in range(2*N-2)], dtype=np.int64)
X = bsr_matrix((data, (R, C)), shape=(N, N), dtype=np.uint64)

ans = spsolve(X, A)

print(*[int(ans[i]) for i in range(-1, N-1)], sep = " ")

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

int main() {
  std::string s;
  std::cin >> s;

  for (int i = 1; i < s.size(); i++) {
    int l = s.size() - i;
    if (l % 2 == 1) {
      continue;
    }
    bool f = true;
    for (int j = 0; j < l / 2; j++) {
      if (s[j] != s[j + l / 2]) {
        f = false;
        break;
      }
    }
    if (f) {
      std::cout << l << std::endl;
      return 0;
    }
  }
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int bse1 = 133;
const int maxn = 19660820;
const int bse2 = 233;
const int mod1 = 19620817;
const int mod2 = 19660813;
#define ull unsigned long long
int n;
struct edge {
	char s[20];
	int h1,h2;
	int len;
}a[110];

inline ull get_hash1(char *s,int len) {
	ull ans = 0;
	for(int i = 1;i <= len; ++i) {
		ans = (ans * bse1 + (ull)s[i]) % mod1;
	}
	return ans;
}

inline ull get_hash2(char *s,int len) {
	ull ans = 0;
	for(int i = 1;i <= len; ++i) {
		ans = (ans * bse2 + (ull)s[i]) % mod2;
	}
	return ans;
}
;
int hsh1[maxn];
int hsh2[maxn];
bool vis1[maxn];
bool vis2[maxn];
int main () {
	int n;
	scanf("%d",&n);
	for(int i = 1;i <= n; ++i) {
		scanf("%s",a[i].s + 1);
		a[i].len = strlen(a[i].s + 1);
	}
	for(int i = 1;i <= n; ++i) {
		a[i].h1 = get_hash1(a[i].s,a[i].len) % mod1;
		a[i].h2 = get_hash2(a[i].s,a[i].len) % mod2;
	}
	//cout<<1<<endl;
	for(int i = 1;i <= n; ++i) {
		//cout<<a[i].h1<<' '<<a[i].h2<<endl;
		if(i == 1) {
			vis1[a[i].h1] = 1;
			vis2[a[i].h2] = 1;
		}
		else {
			if(vis1[a[i].h1] || vis2[a[i].h2]) {
				cout<<"No"<<endl;
				return 0;
			}
			else {
				if(a[i - 1].s[a[i - 1].len] != a[i].s[1]) {
					cout<<"No"<<endl;
					return 0;
				}
				else {
					vis1[a[i].h1] = 1;
					vis2[a[i].h2] = 1;
				}
			}
		}
	}
	puts("Yes");
	return 0;
}


Measured memory_bytes: 37120
using System;

class Program
{
    static void Main()
    {
        int m;
        int f;
        int r;

        while (2 > 1)
        {
            string[] str = Console.ReadLine().Split();
            m = int.Parse(str[0]);
            f = int.Parse(str[1]);
            r = int.Parse(str[2]);

            if (m == -1 && f == -1 && r == -1)
                break;

            if (m == -1 || f == -1)
            {
                Console.WriteLine("F");
            }
            else if (m + f >= 80)
            {
                Console.WriteLine("A");
            }
            else if (m + f >= 65 && m + f < 80)
            {
                Console.WriteLine("B");
            }
            else if (m + f >= 50 && m + f < 65)
            {
                Console.WriteLine("C");
            }
            else if (m + f >= 30 && m + f < 50 && r >= 50)
            {
                Console.WriteLine("C");
            }
            else if (m + f >= 30 && m + f < 50)
            {
                Console.WriteLine("D");
            }
            else if (m + f < 30)
            {
                Console.WriteLine("F");
            }
        }
    }
}

Measured memory_bytes: 8896
using System;
using System.Linq;//リストの使用
using System.Collections.Generic;
using System.Text;//テキストの高速出力に必要
class Program
{
	static void Main()
	{
		int n = int.Parse(Console.ReadLine());
		long[] nums = Array.ConvertAll(Console.ReadLine().Split(' '),long.Parse);
		Array.Sort(nums);
		long answer = 0;
		int first = 0;
		int second = n-1;
		long aimNum = 1073741824;
		bool[] used = new bool[n];
		for(int i = 0; i < n; i++) used[i] = false;
		
		while(true)
		{
			if(n == 1 || aimNum == 1) break;
			first = 0;
			second = n-1;
			while(true)
			{
				if(nums[first] + nums[second] == aimNum)
				{
					if((!used[first]) && (!used[second]))
					{
						answer++;
						used[first] = true;
						used[second] = true;
						first++;
						second--;
					}else if(!used[first])
					{
						second--;
					}else if(!used[second])
					{
						first++;
					}else
					{
						first++;
						second--;
					}
				}else
				{
					if(nums[first] + nums[second-1] < aimNum) first++;
					else second--;
				}
				
				if(first >= second) break;

			}
			aimNum /= 2;
		}
		
		Console.WriteLine(answer);
	}

}

Measured memory_bytes: 28764
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i <= n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()
 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

const ll MOD = 998244353;
const ll inf = 1e18;

int main(){
	cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    double a, b, x;
    cin >> a >> b >> x;
    x /= a;
    double s = a * b, res;
    if (2 * x >= s) {
        double mem = 2 * (s - x) / a;
        res = atan2(mem, a);
    }
    else {
        double mem = 2 * x / b;
        res = atan2(b, mem);
    }
    res *= 180.0 / acos(-1);
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N,M;cin>>N>>M;
  priority_queue<int>A;
  for(int i=0;i<N;i++){int a;cin>>a;A.push(a);}
  for(int i=0;i<M;i++){
    long long a=A.top();
    A.pop();
    A.push(a/2);
  }
  long long ans=0;
  for(int i=0;i<N;i++){ans+=A.top();A.pop();}
  cout<<ans<<endl;
}

Measured memory_bytes: 3904
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<stack>
#include<set>
#include<map>
#include<utility>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<climits>
using namespace std;

typedef long long ll;
const int mod=1e9+7;

int main(){
	int n, d, x;
	cin >> n >> d >> x;
	vector<int> a(n);
	for(int i=0; i<n; i++)
		cin >> a[i];
	int ans=x;
	for(int i=0; i<n; i++){
		for(int j=0; j*a[i]+1<=d; j++)
			ans++;
	}
	cout << ans << endl;
	return 0;
}

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

const long long INF = 1000000000;

typedef long long ll;

#define writeln(n) cout<<n<<"\n";

typedef pair<int, int> P;
typedef pair<string, int> Psi;


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

	int n;cin>>n;

	vector<int> d(n);

	for(int i=0; i<n; i++){
		cin>>d[i];
	}
	int ans =0;
	for(int i=0; i<n; i++){
		for(int j=i+1; j<n; j++){
			 ans += d[i]*d[j];

		}
	}
	writeln(ans);

}




Measured memory_bytes: 256
#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
//long long int countt[200003];
#include<ext/pb_ds/assoc_container.hpp> // include the associative containers or group of templates such as set, multimap, map etc.
#include<ext/pb_ds/tree_policy.hpp> // include the tree_order_statistics_node update
using namespace __gnu_pbds; //necessary for the GNU based Policy based data structures.
typedef tree<pair<int,int> ,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

#define int long long
#define endl "\n"


signed main()
{
    FAST;
    
    int i=0,j=0,k=0,n=0,m=0,count=0,temp=0;
    int temp1=0,temp2=0,temp3=0,x=0,l=0,y=0,sum=0;
    int left=0,up=0,down=0,start=0,end=0,r=0,q=0,total=0;
    int maxx=0,minn=0,curr=0,ans=0,places=0,zeroes=0,low=0,high=0;
    int prev=0,mid=0,z=0,d=0,val=0,pos=0,shift=0,h=0,right=0,var=0;
    
    cin>>n>>m;
    cin>>x;
    int cost[n];
    int a[n][m];
    
    for(i=0;i<n;i++)
    {
        cin>>cost[i];
        for(j=0;j<m;j++)
        {
            cin>>a[i][j];
        }
    }
    
    ans=1e15;
    
    
    
    
    for(i=0;i<pow(2,n);i++)
    {
        //cout<<i<<endl;
        vector<int> vect(m);
        count=0;
        for(j=0;j<m;j++)
        {
            vect[j]=0;
        }
        for(j=0;j<n;j++)
        {
            if(((i)&((int)pow(2,j))))
            {
                count+=cost[j];
                for(z=0;z<m;z++)
                {
                    vect[z]+=a[j][z];
                }
                
            }
            
        }
        
        bool flag=true;
        for(j=0;j<m;j++)
        {
            if(vect[j]<x)
            {
                flag=false;
                break;
            }
        }
        
        if(flag) ans=min(ans,count);
        
    }
    
    if(ans==1e15) ans=-1;
    
    cout<<ans<<endl;
    
    
}

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

#define fastIO ios::sync_with_stdio(false);cout.tie(0);cin.tie(0);
#define endl '\n'
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define MP make_pair
#define inf INT_MAX
#define minf INT_MIN

typedef long long int lli;

ofstream outfile;
ifstream infile;

int n;
int data[100002];
string s;

bool checker()
{
	int i;
	for(i = 2; i < n-1; ++i)
	{
		if(data[i] == 1)
		{
			if(s[i-1] == 'o')
				data[i+1] = data[i-1];
			else{
				if(data[i-1] == 1)
					data[i+1] = 2;
				else
					data[i+1] = 1;
			}
		}
		else
		{
			if(s[i-1] == 'x')
				data[i+1] = data[i-1];
			else
			{
				if(data[i-1]==1)
					data[i+1] = 2;
				else
					data[i+1] = 1;
			}
		}
	}
	if(data[n] == 1)
	{
		if(s[n-1] == 'o')
		{
			if(data[1] != data[n-1])
				return false;
		}
		else
		{
			if(data[1] == data[n-1])
				return false;
		}
	}
	else
	{
		if(s[n-1] == 'x')
		{
			if(data[1] != data[n-1])
				return false;
		}
		else
		{
			if(data[1] == data[n-1])
				return false;
		}
	}
	if(data[n-1] == 1)
	{
		if(s[n-2] == 'o')
		{
			if(data[n-2] != data[n])
				return false;
		}
		else
		{
			if(data[n-2] == data[n])
				return false;
		}
	}
	else
	{
		if(s[n-2] == 'x')
		{
			if(data[n-2] != data[n])
				return false;
		}
		else
		{
			if(data[n-2] == data[n])
				return false;
		}
	}

	if(data[1] == 1)
	{
		if(s[0] == 'o')
		{
			if(data[2] == data[n])
				return true;
			return false;
		}
		else
		{
			if(data[2] != data[n])
				return true;
			return false;
		}
	}
	else
	{
		if(s[0] == 'x')
		{
			if(data[2] == data[n])
				return true;
			return false;
		}
		else
		{
			if(data[2] != data[n])
				return true;
			return false;
		}
	}
}

void print()
{
	for(int i = 1; i <= n; ++i)
	{
		if(data[i] == 1)
			cout << 'S';
		else
			cout << 'W';
	}
	cout << "\n";
}
int main()
{
	infile.open("input.txt");
	outfile.open("output.txt");

	cin >> n >> s;

	data[1] = 1;
	if(s[0] == 'o')
	{
		data[n] = 1;
		data[2] = 1;
		if(checker())
		{
			print();
			return 0;
		}
		data[n] = 2;
		data[2] = 2;
		if(checker())
		{
			print();
			return 0;
		}
	}
	else
	{
		data[2] = 2;
		data[n] = 1;
		if(checker())
		{
			print();
			return 0;
		}
		data[2] = 1;
		data[n] = 2;
		if(checker())
		{
			print();
			return 0;
		}
	}

	data[1] = 2;
	if(s[0] == 'x')
	{
		data[2] = 2;
		data[n] = 2;
		if(checker())
		{
			print();
			return 0;
		}
		data[2] = 1;
		data[n] = 1;
		if(checker())
		{
			print();
			return 0;
		}
	}
	else
	{
		data[2] = 2;
		data[n] = 1;
		if(checker())
		{
			print();
			return 0;
		}

		data[2] = 1;
		data[n] = 2;
		if(checker())
		{
			print();
			return 0;
		}
	}
	cout << "-1\n";
	return 0;
}

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

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for(int i = 0; i < N; i++) {
        cin >> A[i];
    }
    int now = 1;
    int count = 0;
    for(int i = 0; i < N; i++) {
        if(A[i] == now) {
            now++;
        } else {
            count++;
        }
    }
    if(count == N) {
        count = -1;
    }
    cout << count << endl;
}

Measured memory_bytes: 1024
#include <stdio.h>

int main(){
    int S[100000];
    int T[50000];
    int n, q, i, count = 0;
    int low, high, mid;

    //input
    scanf("%d",&n);
    for(i = 0; i < n; i++){
      scanf("%d",&S[i]);
    }

    scanf("%d",&q);
    for(i = 0; i < q; i++){
      scanf("%d",&T[i]);
    }
    
    //excution
    for(i = 0; i < q; i++){
      
      low = 0;
      high = n-1;
      
      while(low <= high){
	
	mid = (low + high) / 2;
	if (S[mid] == T[i]) {
	  count++;
	  break;
	}
	else if (S[mid] < T[i]){
	  low = ++mid;
	}
	else high = --mid;
    
      }
      
    }
    
    //output
    printf("%d\n",count);

    return 0;
}


Measured memory_bytes: 2276
#include<bits/stdc++.h>
#define F first
#define S second
using namespace std;

int h, w;
string s[1111];
int data[1111][1111];
typedef pair < int, int > P;
typedef pair < int, P > PP; 
queue < PP > que;

void cnt(int x, int y){

  for(int i=-1;i<2;i++)
    for(int j=-1;j<2;j++)
      if(i+y >= 0 && j+x >= 0) data[i+y][j+x]++;
}

      
int main(){

  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++) if(s[i][j] == '.') cnt(j, i);

  

  for(int i=0;i<h;i++)
    for(int j=0;j<w;j++)
      if(s[i][j] != '.' && data[i][j] >= s[i][j]-'0') que.push( PP(1, P(j, i)) );
      
  int ans = 0;
  while(!que.empty()){
    PP p = que.front(); que.pop();
    int x = p.S.F, y = p.S.S;

    if(s[y][x] == '.') continue;

    ans = max(ans, p.F);
    s[y][x] = '.';
    cnt(x, y);

    for(int i=-1;i<2;i++){
      for(int j=-1;j<2;j++){
	int xx = j+x, yy = i+y;
	if(xx >= 0 && yy >= 0 && s[yy][xx] != '.' && data[yy][xx] >= s[yy][xx]-'0')  que.push( PP(p.F+1, P(xx, yy)) );
      }
    }

  }

  cout << ans << endl;
  
}

Measured memory_bytes: 6632
#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 gcd(int a,int b)
{
 
  int r, tmp;
 
  
 
  /* 自然数 a > b を確認・入替 */
  if(a<b){
    tmp = a;
    a = b;
    b = tmp;
  }
 
  /* ユークリッドの互除法 */
  r = a % b;
  while(r!=0){
    a = b;
    b = r;
    r = a % b;
  }
 
 
 
  return b;
}







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 h,w;
  bool flag=true;
  cin>>h>>w;
  vector<vector<char>> v(h+2,vector<char>(w+2));
  rep(i,h+2) rep(j,w+2) v[i][j]='%';
  
  for(int i=1;i<h+1;i++){
    for(int j=1;j<w+1;j++){
      cin>>v[i][j];
    }
  }
  
  for(int i=1;i<h+1;i++){
    for(int j=1;j<w+1;j++){
      if(v[i][j]=='#'){
        if(v[i-1][j]!='#' && v[i+1][j]!='#' && v[i][j+1]!='#' && v[i][j-1]!='#'){
          flag=false;
          break;
        }
      }
    }
  }
  
  if(flag){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
}
///////////////////////////



Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <time.h>
#include <stdlib.h>
using namespace std;

int main(){
	while(1){
		int a,b,n,aa,bb;
		cin >> n;
		if(n==0) return 0;
		aa=0;
		bb=0;
		for(int i=0;i<n;i++){
			cin >> a;
			cin >> b;
			if(a>b) aa+= a+b;
			else if(b>a) bb += a+b;
			else{
				aa+=a;
				bb+=b;
			}
		}
		printf("%d %d\n",aa,bb);
	}
	return 0;
}


Measured memory_bytes: 3124
#include <bits/stdc++.h>
#define all(r) r.begin(),r.end()
using namespace std;
typedef vector<string> vss;
struct Solution {
    void solve(std::istream& in, std::ostream& out) {
        string s, t;
        in >> s;
        in >> t;
        int len = t.size();
        vss ans;
        for (int i = s.size() - len; i >= 0; i--) {
            int cnt = 0;
            for (int j = 0; i + j < s.size() && j < t.size(); j++) {
                cnt += s[i + j] == t[j] || s[i + j] == '?';
            }
            if (len == cnt) {
                string o = s;
                for (int k = i; k < i + len; k++) {
                    o[k] = t[k - i];
                }
                for (int k = 0; k < o.size(); k++) {
                    if (o[k] == '?') {
                        o[k] = 'a';
                    }
                }
                ans.emplace_back(o);
            }
        }
        if (ans.size() > 0) {
            sort(all(ans));
            out << ans.front() << '\n';
        }
        else {
            out << "UNRESTORABLE" << '\n';
        }
    }
};
void solve(std::istream& in, std::ostream& out) {
    out << std::setprecision(12);
    Solution solution;
    solution.solve(in, out);
}
#include <fstream>
#include <iostream>
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    istream& in = cin;
    ostream& out = cout;
    solve(in, out);
    return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

using static Input;
using static Util;
class Program
{
    static int H,N;
    static int[] A, B;

    static void INPUT()
    {
        H = NextInt();
        N = NextInt();
        A = new int[N];
        B = new int[N];
        for (int i = 0; i < N; i++)
        {
            A[i] = NextInt();
            B[i] = NextInt();
        }
    }

    static void OUT()
    {
        var dp = new int[N + 1, H + 1];
        for (int i = 0; i <= 0; i++)
            for (int j = 0; j <= H; j++)
                dp[i,j] = INF;

        for (int i = 0; i < N; i++)
        {
            for (int j = 1; j <= H; j++)
            {
                dp[i + 1, j] = Math.Min(dp[i, j], dp[i + 1, Math.Max(0, j - A[i])] + B[i]);
            }
        }
        Console.WriteLine(dp[N,H]);
    }
    static void Main(string[] args)
    {
#if DEBUG  
        //TESTINPUT();
        INPUT();

#else
        INPUT();
#endif
        OUT();
    }

    static void TESTINPUT()
    {
    }

}

public class Input
{
    public const long MOD = 1000000007;
    public const int INF = 1000000007;
    private static Queue<string> q = new Queue<string>();
    private static void Confirm() { if (q.Count == 0) foreach (var s in Console.ReadLine().Split(' ')) q.Enqueue(s); }
    public static int NextInt() { Confirm(); return int.Parse(q.Dequeue()); }
    public static long NextLong() { Confirm(); return long.Parse(q.Dequeue()); }
    public static string NextString() { Confirm(); return q.Dequeue(); }
    public static double NextDouble() { Confirm(); return double.Parse(q.Dequeue()); }
    public static int[] LineInt() { return Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); }
    public static long[] LineLong() { return Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); }
    public static string[] LineString() { return Console.ReadLine().Split(' ').ToArray(); }
    public static double[] LineDouble() { return Console.ReadLine().Split(' ').Select(double.Parse).ToArray(); }
}

class Util
{

}




Measured memory_bytes: 50144
use std::io;

fn main() {
	let mut buf = String::new();
	io::stdin().read_line(&mut buf).expect("");
	let s:Vec<char> = buf.trim().chars().collect();
	for i in s {
		if i == '1' {
			print!("9");
		}else{
			print!("1");
		}
	}
	print!("\n");
}

Measured memory_bytes: 4352