akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <stdio.h>
#include <list>
#include <numeric>
#include <stack>
#include <queue>
#include <tuple>
#include <bitset>
#include <map>
#include <math.h>
//　ceil(a/b)   (a + (b - 1))/ b
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
typedef long long ll;
typedef pair<int,int> P;
const int inf=1000000007;
const ll mod=1000000007;
const double PI=3.14159265358979323846;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};

ll gcd(ll a, ll b){
  if (b==0) return a;
  else return gcd(b,a%b);
}

int cans(bool f){
  if(f) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}




int grid[100][100];
int ans[100][100];
int a,b,h,w;


int main(){
  cin >> h >> w;
  char c;
  rep(i,h){
    rep(j,w){
      ans[i][j] = inf;
      cin >> c;
      if(c == '.') grid[i][j] = 0;
      else grid[i][j] = 1;
    }
  }
  if(grid[0][0] == 1) ans[0][0] = 1;
  else ans[0][0] = 0;
  
  rep(i,h)rep(j,w){
    if(i>0){
      int a = ans[i-1][j];
      if(grid[i][j]^grid[i-1][j]) a++;
      ans[i][j] = min(ans[i][j],a);
    }
    if(j>0){
      int a = ans[i][j-1];
      if(grid[i][j]^grid[i][j-1]) a++;
      ans[i][j] = min(ans[i][j],a);
    }
  }
  
  cout << (ans[h-1][w-1]+1)/2 << endl;
  return 0;
}



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


int main()
{	
	int a[5];
	cin >> a[0] >>a[1]>>a[2]>>a[3]>>a[4];
	if(a[0]<a[2]+a[4]||0>a[2]-a[4]||0>a[3]-a[4]||a[1]<a[3]+a[4])
		cout << "No" << endl;
	else cout << "Yes" << endl;
	return 0;
}

Measured memory_bytes: 3132
# coding:utf-8

n,y = map(int, input().split())

def solve():
    if y%1000 != 0:
        return -1,-1,-1
    for i in range(y//10000+1)[::-1]:
        for j in range((y-10000*i)//5000+1)[::-1]:
            k = n - i - j
            sum = 10000*i + 5000*j + 1000*k
            if sum == y:
                return i,j,k
    return -1,-1,-1

a,b,c = solve()
print(a,b,c)


Measured memory_bytes: 3060
#include<stdio.h>


typedef struct node{  
  int parent;
  int right;
  int left;


} tree1;

tree1 A[1000000];
int number;

int D[1000000];


void depth(int i,int p){
  int d=0;
  D[i]=p;


  if(A[i].right!=-10)
    {depth(A[i].right,p);}
  if(A[i].left!=-10)
    {depth(A[i].left,p+1);}
}






int main(){



  
  scanf("%d",&number);
  

  int i,j;

  

  for(i=0;i<number;i++){
    

    A[i].parent=A[i].right=A[i].left=-10;
  }


  
  int n;


  int node,c_degree;
  int c_node;

  int l;
 

  //節点番号と子の次数を入れていく
  for(i=0;i<number;i++){
    scanf("%d%d",&node,&c_degree);



    //子の節点番号を入れていく
    for(j=0;j<c_degree;j++){
      scanf("%d",&c_node);

    
      
      if(j==0){A[node].left=c_node;}

      else{A[ l ].right=c_node;}
	
       	l=c_node;
	A[c_node].parent=node;
      }


    
    }
   
  

  int r;

  
  for(i=0 ; i<number ; i++){
    if(A[i].parent==-10){r=i;}
  }

  
  depth(r,0);


  for(i=0;i<number;i++){
    printf("node %d: parent = ",i);
    if(A[i].parent==-10){A[i].parent=-1;
      printf("%d, depth = %d,",A[i].parent,D[i]);
      A[i].parent=-10;}
    else {printf("%d, depth = %d,",A[i].parent,D[i]);}

    
    if(A[i].parent==-10){printf(" root, [");}
    else if(A[i].left==-10){printf(" leaf, [");}
    else {printf(" internal node, [");}

    int h;

    for(j=0,h=A[i].left;h!=-10;j++,h=A[h].right){
      if(j>0){printf(",");}
      if(j==0)printf("%d",h);
      else {printf(" %d",h);}
      

    }
    printf("]\n");

  }

  
  return 0;
}





Measured memory_bytes: 6392
#include <bits/stdc++.h>
   
using namespace std;
#define ll long long
#define ld long double
#define pll pair<long long,long long>
#define vll vector<long long>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define deb(x) cout << #x << "=" << x << endl
#define F(i,a,b) for(ll i=a;i<=b;i++)
#define RF(i,a,b) for(ll i=a;i>=b;i--)
#define in(a,n) F(i,0,n-1)cin>>a[i]
#define vi vector<int>
#define out(a,n) F(i,0,n-1)cout<<a[i]<<" ";cout<<endl
#define mod 1000000007
#define int long long
set < ll> primes;
 int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int n;
bool isvalid(int x,int y){
  return (x>=0 and x<n and y>=0 and y<n);
}
void Sieve(ll n) 
{ 
    bool prime[n+1];
	for(ll i=0;i<n+1;++i)
		prime[i]=true;
    for (ll p=2;p*p<=n;++p) 
    {
        if (prime[p] == true) 
        {  
            for (ll i=2*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    }  
    for(ll p=2; p<=n; p++) 
       if (prime[p]) 
		primes.insert(p);  
}

ll gcd(ll a, ll b) 
{ 
    if (a == 0) 
        return b; 
        return gcd(b % a, a); 
} 
ll powermod(ll x, ll y){
    if(y==0)
    return 1;
        
    if(y%2==0)
    return (powermod(x,y/2)*powermod(x,y/2))%mod;
    else
    return (((powermod(x,y/2)*powermod(x,y/2))%mod)*x)%mod;
}

 
 

int32_t main()
{
	ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int h,n;
    cin>>h>>n;
    int a[n],c[n];
    for(int i=0;i<n;i++)cin>>a[i]>>c[i];
    int ma=*max_element(a,a+n);
    int dp[h+ma+1];
    for(int i=0;i<=h+ma;i++)dp[i]=INT_MAX;
    
    dp[0]=0;
    for(int i=0;i<=h+ma;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(a[j]<=i)
            {
                dp[i]=min(dp[i],dp[i-a[j]]+c[j]);
            }
        }
    }
    int ans=INT_MAX;
    for(int i=h;i<=h+ma;i++)
    {
       // cout<<dp[i]<<'\n';
       ans=min(ans,dp[i]);
    }
    cout<<ans<<'\n';
    //for(int i=0;i<=h;i++)cout<<dp[i]<<'\n';
    
}

Measured memory_bytes: 384
#include <vector>
#include <iostream>
using namespace std;
const int mod = 1000000007;
int N, A, B, C, D, fact[2009], inv[2009], factinv[2009], ncr[2009][2009], dp[2009][2009];
int main() {
	fact[0] = 1;
	for (int i = 1; i <= 2005; i++) fact[i] = 1LL * fact[i - 1] * i % mod;
	inv[1] = 1;
	for (int i = 2; i <= 2005; i++) inv[i] = 1LL * inv[mod % i] * (mod - mod / i) % mod;
	factinv[0] = 1;
	for (int i = 1; i <= 2005; i++) factinv[i] = 1LL * factinv[i - 1] * inv[i] % mod;
	ncr[0][0] = 1;
	for (int i = 1; i <= 2005; i++) {
		for (int j = 0; j <= i; j++) {
			ncr[i][j] = ncr[i - 1][j];
			if (j) {
				ncr[i][j] += ncr[i - 1][j - 1];
				if (ncr[i][j] >= mod) ncr[i][j] -= mod;
			}
		}
	}
	cin >> N >> A >> B >> C >> D;
	dp[0][0] = 1;
	for (int i = 0; i <= B - A; i++) {
		for (int j = 0; j <= N; j++) {
			dp[i + 1][j] = dp[i][j];
			int prod = 1;
			for (int k = 1; k < C && j - (i + A) * k >= 0; k++) {
				prod = 1LL * prod * ncr[N - j + (i + A) * k][i + A] % mod;
			}
			for (int k = C; k <= D && j - (i + A) * k >= 0; k++) {
				int p = j - (i + A) * k;
				int res = dp[i][p];
				prod = 1LL * prod * ncr[N - j + (i + A) * k][i + A] % mod;
				res = 1LL * res * prod % mod;
				res = 1LL * res * factinv[k] % mod;
				dp[i + 1][j] += res;
				if (dp[i + 1][j] >= mod) dp[i + 1][j] -= mod;
			}
		}
	}
	cout << dp[B - A + 1][N] << endl;
	return 0;
}

Measured memory_bytes: 22016
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
using ll = long long;
using VL=vector<ll>;

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
const long long INF =  999999999;

template <typename T>
vector<T> topologicalsort(vector<vector<T>> g,T v){
  T h[v];
  fill(h,h+v,0);
  //頂点は0~N-１と番号付けられていることに注意
  REP(i,g.size()){
    REP(j,g[i].size()){
      h[g[i][j]]++;
    }
  }
  
  stack <T> st;
  REP(i,v)if(h[i]==0)st.push(i);

  vector<T> ans;
  while(st.size()){
    T s=st.top();st.pop();
    ans.push_back(s);
    REP(i,g[s].size()){
      h[g[s][i]]--;
      if(h[g[s][i]]==0)st.push(g[s][i]);
    }
  }
  return ans;
}


int main(){
  ll N,M;
  cin>>N>>M;
  vector<vector<ll>> g(N);
  ll s,t;
  REP(i,M){
    scanf("%lld %lld",&s,&t);
    g[s].push_back(t);
  }
  vector <ll> ans;
  ans=topologicalsort(g,N);
  REP(i,ans.size()){
    cout << ans[i]<<endl;
  }
}


Measured memory_bytes: 4668
#include<stdio.h>
int dp[100005][3];
int ar[100005][3];
class solution {
private:
	int n;
	int serc(int x, int p) {
		if (x == n) return 0;
		if (x == 0) {
			int res = (1 << 31);
			for (int i = 0; i < 3; i++) {
				res = max(res, ar[0][i] + serc(1, i));
			}
			return res;
		}
		if (dp[x][p] != -1) return dp[x][p];
		dp[x][p] = (1 << 31);
		for (int i = 0; i < 3; i++) {
			if (i != p) dp[x][p] = max(dp[x][p], ar[x][i] + serc(x + 1, i));
		}
		return dp[x][p];
	}
	int max(int a, int b) {
		if (a > b) return a;
		return b;
	}
public:
	solution() {
		scanf("%d", &n);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < 3; j++) {
				scanf("%d", &ar[i][j]);
				dp[i][j] = -1;
			}
		}
		printf("%d\n", serc(0, 69));
	}
};

#ifndef L0C4L
int main() {
	solution();
	return 0;
}
#endif

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

int main(){
    ll n;
    cin >> n;
    rep(i,n){
        ll x;
        cin >> x;
        if(x%2==0){
            if(x%3==0||x%5==0) continue;
            else{
                puts("DENIED");
                return 0;
            }
        }
    }
    puts("APPROVED");

    return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main {
	private	static	BufferedReader	br = null;

	static {
		br = new BufferedReader(new InputStreamReader(System.in));
	}
 
    /**
     * @param args
     */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int	num = parseNum();

		for (int i = 0; i < num; i++) {
			solve(parsePos());
		}
	}

	private static void solve(int[][] pos) {
		if (isInner(pos[0], pos[1], pos[2], pos[3]) != isInner(pos[0], pos[1], pos[2], pos[4])) {
			System.out.println("OK");
		} else {
			System.out.println("NG");
		}
	}

	private static boolean isInner(int[] ia, int[] ib, int[] ic, int[] ip) {
        int	n1 = getCrossSign(ia, ib, ip);
        int	n2 = getCrossSign(ib, ic, ip);
        int	n3 = getCrossSign(ic, ia, ip);

        return ((n1 == n2) && (n2 == n3));
	}
 
	private static int getCrossSign(int[] ia, int[] ib, int[] ip) {
		int[]    iab = { ib[0] - ia[0], ib[1] - ia[1] };
		int[]    iap = { ip[0] - ia[0], ip[1] - ia[1] };
		return ( getCross(iab, iap) >= 0 ) ? 1 : -1;
	}
 
	private static double getCross(int[] iab, int[] iap) {
		return iab[0] * iap[1] - iab[1] * iap[0];   // x1*x2 + y1*y2
	}

	private static int[][] parsePos() {
		int[][]	pos = null;
		String	str = null;

		if ((str = parseStdin()) != null) {
			String[]	lns = str.split(" ");

			pos = new int[5][2];
			for (int i = 0; i < pos.length; i++) {
				pos[i][0] = Integer.parseInt(lns[i*2]);
				pos[i][1] = Integer.parseInt(lns[i*2+1]);
			}
		}
 
		return pos;
	}

	private static int parseNum() {
		int		param = 0;
		String	strin = null;

		if ((strin = parseStdin()) != null) {
			param = Integer.parseInt(strin);
		}
 
		return param;
	}

	private static String parseStdin() {
        String  stdin = null;
        
        try {
        	String  tmp = br.readLine();
        	if (tmp != null) {
            	if (!tmp.isEmpty()) {
            		stdin = tmp;
            	}
        	}
        }
        catch (IOException e) {}
 
        return stdin;
	}
}

Measured memory_bytes: 42776
{-# OPTIONS_GHC -O2 #-}
{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE BangPatterns #-}
module Main where

import           Data.List
import           Control.Monad
import           Debug.Trace
import qualified Data.ByteString.Char8         as BC
import           Data.Maybe                     ( fromJust, fromMaybe )
import qualified Data.Set                      as S
import qualified Data.IntMap.Strict            as IM
import qualified Data.IntMap.Lazy            as IML
import qualified Data.Map.Strict               as M
import           Data.Char
import qualified Data.Array.IArray as A
import qualified Data.Array.Unboxed as UA
import Data.Bits
import Control.Monad.State.Strict
import qualified Data.Array.ST as STA
import qualified Data.Array.IO as IOA
import qualified Data.Array.MArray as MA
import Control.Monad.ST
import System.IO (stdin)
import Control.Arrow
import qualified Data.Vector.Unboxed as UV
import qualified Data.Vector.Generic as GV



readTuple2 :: IO (Int, Int)
readTuple2 = do
    [a, b] <- readInts
    return (a, b)

readTuple3 :: IO (Int, Int, Int)
readTuple3 = do
    [a, b, c] <- readInts
    return (a, b, c)

readInt :: IO Int
readInt = fst . fromJust . BC.readInt <$> BC.getLine

readInts :: IO [Int]
readInts = map (fst . fromJust . BC.readInt) . BC.words <$> BC.getLine

split :: (a -> Bool) -> [a] -> [[a]]
split f [] = []
split f as =
    let (fo, la) = span f as
        las      = case la of
            [] -> []
            xs -> split f $ tail xs
    in  case fo of
            [] -> las
            xs -> xs : las

solve :: Int -> BC.ByteString -> Int
solve n as = minimum eachnum where
    scanner (east, west) 'E' =  (east +1, west) 
    scanner (east,west) _ = (east, west+1)
    lrsumacc :: UV.Vector (Int, Int)
    lrsumacc = GV.fromList $ scanl' scanner (0, 0) $ BC.unpack as
    rlsumacc :: UV.Vector (Int, Int)
    rlsumacc = GV.fromList $ scanr (flip scanner) (0, 0) $ BC.unpack as
    eachnum = (\i -> (snd $ lrsumacc GV.! (i - 1)) + (fst $ rlsumacc GV.! i)) <$> [1..n]

main = do
    n <- readInt
    s <- BC.getLine
    print $ solve n s


Measured memory_bytes: 89468
#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
using ll = long long;
#ifdef KEV
#define DE(i, e) cerr << #i << ' ' << i << e
void debug(auto L, auto R) { while (L < R) cerr << *L << " \n"[L+1==R], ++L; }
#else
#define DE(...) 0
void debug(...) {}
#endif
const int maxn = 300010, x = 213247, p = 1e9+7;
ll v[maxn], hs[maxn], n, k, m, pf[maxn], po[maxn]{1};
ll res;
ll gh(int l, int len) {
	return (hs[l+len-1] - hs[l-1] * po[len] % p + p) % p;
}
signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> v[1] >> m;
	for (int i = 2;i <= m+m;++i) 
		v[i] = v[i-1] * v[i-1] % m;
	for (int i = 1;i <= m+m;++i) {
		hs[i] = (hs[i-1] * x + v[i]) % p;
		pf[i] = pf[i-1] + v[i];
		po[i] = po[i-1] * x % p;
	}
	if (n <= m+m) 
		return cout << pf[n] << '\n', 0;
	if (v[m] == 0) 
		return cout << pf[m] << '\n', 0;


	int cy = -1;
	for (int len = 1;len <= m;++len) {
		if (gh(m+m-len+1, len) == gh(m+m-len-len+1, len)) {
			cy = len;
			break;
		}
	}
	DE(cy, '\n');
	assert(cy != -1);
	int e = m+m;
	ll over = n - e;
	ll sum = pf[e] - pf[e-cy];
	res = pf[e] + over / cy * sum;
	over %= cy;
	DE(over, '\n');
	for (int h = 0, i = m+m-cy+1;h < over;++h, ++i) {
		res += v[i];
		//cerr << i << ' ';
	}
	cout << res << '\n';
}


Measured memory_bytes: 9824
import sys
input = sys.stdin.readline
from collections import deque

def main():
    n=int(input())
    ab=[list(map(int,input().split())) for _ in range(n-1)]
    l=[[] for _ in range(n+1)]
    for i in range(n-1):
        l[ab[i][0]].append(ab[i][1])
    col=[0]*(n+1)
    chk=deque([1])
    while chk:
        x=chk.popleft()
        c=0
        for y in l[x]:
            c+=1
            if col[x]==c:
                c+=1
            col[y]=c
            chk.append(y)
    print(max(col))
    for i in range(n-1):
        print(col[ab[i][1]])
    
if __name__ == '__main__':
    main()

Measured memory_bytes: 36784
#include<iostream>
#include<vector>
#include<algorithm>

typedef long long ll;

using namespace std;

ll gcd(ll a,ll b){
  if(b==0)return a;
  return gcd(b, a%b);
}

ll lcm(ll a,ll b){
  return a*b/gcd(a,b);
}

ll lcm_n(vector<ll> num){
  ll l=num[0];
  for(int i=0;i<num.size();i++)l=lcm(l,num[i]);
  return l;
}

ll func(ll a, ll m){
  ll cnt=1,x=a%m;
  while(x!=1)x=(a*x)%m,cnt++;
  return cnt;
}

int main(void){

  ll m[4],a[4];

  while(true){

    int b=0;
    for(int i=1;i<4;i++){
      cin >> a[i] >> m[i];
      b=a[i]+m[i];
    }
    if(b==0)break;
    
    ll cnt=0,x=1,y=1,z=1;
    vector<ll>num;

    for(int i=1;i<4;i++)
    num.push_back(func(a[i],m[i]));

    cout << lcm_n(num) << endl;
    //cout << lcm(lcm(num[0],num[1]),num[2])<< endl;
  }

  return 0;
}

Measured memory_bytes: 1212
N = int(input())
X = list(map(int,input().split()))
sX=sorted(X)
ans = []
ans.append(sX[N//2-1])
ans.append(sX[N//2])
for xi in X:
    if xi <= ans[0]:
        print(ans[1])
    else:
        print(ans[0])



Measured memory_bytes: 93780
using namespace std;

#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <algorithm>
#include <utility>
#include <functional>
#include <queue>
#include <cmath>
#include <numeric>
#include <map>
using namespace std;


int main(void){
	int N;

	cin >> N;

  multimap<int, int> BA;
  
  for (int i = 0; i<N;i++) {
    int A, B;
    
    cin >> A >> B;
    BA.emplace(B, A);
  }
  
  int now = 0;
  for (auto&& i : BA) {
    now += i.second;
    
    if (now > i.first) {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;

	return 0;
}


Measured memory_bytes: 9728
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
	ios::sync_with_stdio(false);
	int k,a,b;
	cin>>k>>a>>b;
	int v1 = a/k;
	int v2 = b/k;
	if(abs(v2-v1)>0 || v1*k==a || v2*k==b){
		cout<<"OK"<<'\n';
	}
	else{
		cout<<"NG"<<'\n';
	}
	return 0;
}

Measured memory_bytes: 3688
#include <stdio.h>

const int DX[3][13] = {
    {0, -1, 0, 1, 0},
    {-1, 0, 1, -1, 0, 1, -1, 0, 1},
    {0, -1, 0, 1, -2, -1, 0, 1, 2, -1, 0, 1, 0}
};
const int DY[3][13] = {
    {-1, 0, 0, 0, 1},
    {-1, -1, -1, 0, 0, 0, 1, 1, 1},
    {-2, -1, -1, -1, 0, 0, 0, 0, 0, 1, 1, 1, 2}
};
const int SIZE[3] = {5, 9, 13};

int paper[16][16];

int main(void)
{
    int x, y, s;
    int maxi;
    int white;
    int i, j;

    while (~scanf("%d,%d,%d", &x, &y, &s)){
        int i;

        for (i = 0; i < SIZE[s - 1]; ++i){
            int tx = x + DX[s - 1][i];
            int ty = y + DY[s - 1][i];

            if (tx < 0 || 10 <= tx || ty < 0 || 10 <= ty){
                continue;
            }

            ++paper[ty][tx];
        }
    }

    white = maxi = 0;
    for (i = 0; i < 10; ++i){
        for (j = 0; j < 10; ++j){
            if (paper[i][j] == 0){
                ++white;
            }
            if (maxi < paper[i][j]){
                maxi = paper[i][j];
            }
        }
    }

    printf("%d\n", white);
    printf("%d\n", maxi);

    return (0);
}

Measured memory_bytes: 600
#include<stdio.h>

long long N,W;
long long w[110],v[110];
long long dp[110][100010];

long long min(long long x,long long y){
	if(x<y)return x;
	return y;
}

int main(){
	scanf("%lld%lld",&N,&W);
	for(long long i=0;i<N;i++)scanf("%lld%lld",&w[i],&v[i]);
	
	for(long long i=0;i<110;i++)for(long long j=0;j<100010;j++){
		dp[i][j]=9999999999999;
	}
	
	dp[0][0]=0;
	
	for(long long i=0;i<N;i++){
		for(long long j=0;j<100010;j++){
			if(j>=v[i]){
				dp[i+1][j]=min(dp[i][j-v[i]]+w[i],dp[i][j]);
			}
			else dp[i+1][j]=dp[i][j];
		}
	}
	
	for(int i=100009;i>=0;i--){
		if(dp[N][i]<=W){
			printf("%d\n",i);
			return 0;
		}
	}
	
	return 0;
}

Measured memory_bytes: 86144
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iso646.h>
#include <map>
#include <math.h>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>

#ifndef M_PI
#define M_PI 3.14159265358979
#endif
#define deg_to_rad(deg) (((deg) / 360) * 2 * M_PI)
#define rad_to_deg(rad) (((rad) / 2 / M_PI) * 360)

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;
typedef vector<long long> vll;
typedef pair<long long, long long> pll;

const ll INF = 1e15;
const ll MOD = 1e9 + 7;

int main() {

    string N;
    cin >> N;
    for(size_t i = 0; i < 3; i++) {
        if(N[i] == '7') {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3132
#include <stdio.h>

int main(void)
{
	int a,b,c;
	int i;
	int times;
	
	scanf("%d",&times);
	
	for(i=0;i<times;i++)
	{
		scanf("%d %d %d",&a,&b,&c);
		
		if(0.0 == (double)(a*a + b*b - c*c)/(2*a*b))
		{
			printf("YES\n");
		}
		else if(0.0 == (double)(b*b + c*c - a*a)/(2*b*c))
		{
			printf("YES\n");
		}
		else if(0.0 == (double)(c*c + a*a - b*b)/(2*c*a))
		{
			printf("YES\n");
		}
		else
		{
			printf("NO\n");
		}
	}
	
	return 0;
}

Measured memory_bytes: 2680
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <climits>
#include <map>
using namespace std;

int main() {
    string str;
    
    cin >> str;
    
    int len = (int)str.size() - 2;
    
    cout << str[0] << len << str[str.size() - 1] << endl;
}

Measured memory_bytes: 256
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c for j in range(b)] for i in range(a)]
def list3d(a, b, c, d): return [[[d for k in range(c)] for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e for l in range(d)] for k in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10**9)
INF = 10**19
MOD = 10**9 + 7
EPS = 10**-10

N = INT()
U = []
V = []
for i in range(N):
    x, y = MAP()
    U.append(x+y)
    V.append(x-y)

U.sort()
V.sort()
ans = max(U[-1]-U[0], V[-1]-V[0])
print(ans)


Measured memory_bytes: 93800
n=int(input())
d={'S':[0]*13,'H':[0]*13,'C':[0]*13,'D':[0]*13}
for i in range(n):
    suit,rank=input().split()
    d[suit][int(rank)-1]=1
for k,v in d.items():
    for i in range(13):
        if v[i]==0:
            print(k,i+1)



Measured memory_bytes: 5600
N = int(input())
h = input().split()
h = [int(i) for i in h]

res = 0
while True:
    if max(h) == 0:
        break

    i = 0
    while(i<N):
        if h[i] == 0:
            i += 1
        else:
            res += 1
            while (i < N) and (h[i] > 0):
                h[i] -= 1
                i += 1
print(res)

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <tuple>
#include <stack>
#include <bitset>
#include <utility>
#include<iomanip>
// #include <numeric>
using namespace std;



typedef unsigned long ul;
typedef unsigned long long ull;
typedef long long ll;
typedef vector<ll> vint;
typedef vector<vector<ll>> vvint;
typedef vector<string> vstring;
typedef vector<vector<string>> vvstring;
typedef vector<char> vchar;
typedef vector<vector<char>> vvchar;
typedef pair<ll,ll> pint;
typedef vector<pint> vpint;

#define rep(i,n) for(ll i=0;i<n;i++)
#define repf(i,f,n) for(ll i=f;i<n;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define INT_MAX 2147483647
#define LLONG_MAX 9223372036854775807
#define vmax(vec) *max_element(vec.begin(), vec.end())
#define vmin(vec) *min_element(vec.begin(), vec.end())
#define vsort(vec) sort(vec.begin(), vec.end())
#define vsortgr(vec) sort(vec.begin(), vec.end(), greater<ll>())
#define DIVIDER 1000000007


//
// struct Node{
//   vint children;
//   ll index;
//   ll prop;
// };



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

// ll X,Y,Z,K;
// ll pmax = 30000000000;
// vint A,B,C;




// int binary_search(int key){
//  //isOKを満たす要素のうち最小のインデックスを返す。（要ソート）
//   int left = -1;
//   int right = N;
//
//   while(right - left > 1){
//     int mid = left + (right - left)/2;
//
//     if(isOK(mid, key)) right=mid;
//     else left=mid;
//   }
//
//   return right;
// }

// ll gcd(ll m, ll n){
//   if(m<n) swap(m,n);
//   if(n==0) return m;
//   return gcd(n, m%n);
// }




int main() {
  cout<<fixed<<setprecision(10);



  ll N;
  cin >> N;
  vector<long double> p(N);
  rep(i,N)cin>>p[i];


  vector<vector<long double>> dp(N, vector<long double>(N+1, 0));

  dp[0][0] = 1 - p[0];
  dp[0][1] = p[0];

  repf(i,1,N){
    rep(j,i+2){
      if(j==0) dp[i][j] = dp[i-1][j]*(1-p[i]);
      else{
        dp[i][j] = dp[i-1][j]*(1-p[i]) + dp[i-1][j-1]*p[i];
      }
    }
  }

  // rep(i,N){
  //   rep(j,N+1){
  //     cout << dp[i][j] <<" ";
  //   }
  //   cout << endl;
  // }

  long double ans = 0.0;
  repf(j,N/2+1,N+1){
    ans+=dp[N-1][j];
  }

  cout << ans << endl;

}

















//


Measured memory_bytes: 141056
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define re register
#define tot ecnt
int L;
struct Front_star{int u,v,w;}e[90];
int ecnt=0;
void add(int u,int v,int w){tot++;e[tot].u=u;e[tot].v=v;e[tot].w=w;}
int main(){
	cin>>L;
	int cnt=0,tmp=L;
	while(tmp)cnt++,tmp/=2;
	for(int i=1;i<cnt;i++)add(i,i+1,0),add(i,i+1,(1<<(i-1)));
	cnt--;
	int ret=L-(1<<cnt);
	int Use=(1<<cnt);
	for(int i=0;i<20;i++){
		if((1<<i)&ret)add(i+1,cnt+1,Use),Use+=(1<<i);
	}
	cout<<cnt+1<<" "<<tot<<'\n';
	for(int i=1;i<=tot;++i){
		cout<<e[i].u<<" "<<e[i].v<<" "<<e[i].w<<'\n';
	}
	return 0;
} 


Measured memory_bytes: 256
(n,),q,*c=$<.map{|s|s.split.map &:to_i}
P=*0..n
F=->x{x==P[x]?x:P[x]=F[P[x]]}
c.map{|x,y|P[F[x]]=F[y]}
p q.count{|x|F[x]==F[q[x-1]]}

Measured memory_bytes: 14068
//*******Abhijit Burman***********//
//Jalpaiguri Government Engineering College//

// Taken From Striver_79
// Never open a ranklist untill and unless you are done with solving problems, wastes 3/4 minuts 
// Donot treat CP as a placement thing, love it and enjoy it, you will succeed for sure. 


#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define ff first
#define ss second
#define mk make_pair
#define MAXX (1000000000000000000+7)
#define mod 1000000007
#define endl "\n"
#define fio ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
void input(ll a[], ll sz) {for(ll i=0;i<sz;i++) cin >> a[i];}
void print(ll a[], ll sz) {for(ll i=0;i<sz;i++) {if (i == sz - 1) cout << a[i] << "\n"; else cout << a[i] << " ";}}
ll dx1[] = {1, 1, 0, -1, -1, -1, 0, 1};
ll dy1[] = {0, 1, 1, 1, 0, -1, -1, -1};

ll dx2[] = {1, 0, -1, 0};
ll dy2[] = {0, 1, 0, -1};

ll mul(ll a, ll b, ll p = mod) {return ((a % p) * (b % p)) % p;}
ll add(ll a, ll b, ll p = mod) {return (a % p + b % p) % p;}
ll power(ll x,ll y,ll p = mod) 
{ 
    ll res = 1;
    x = x % p;
    while (y > 0) 
    {
        if (y & 1) 
            res = (res*x) % p;
        y = y>>1; // y = y/2 
        x = (x*x) % p; 
    } 
    return res; 
} 
ll modInverse(ll n, ll p = mod)
{
    return power(n, p - 2, p);
}
ll ncrMod(ll n, ll r, ll p = mod)
{
    if (r == 0)
        return 1;
    ll fac[n + 1];
    fac[0] = 1;
    for (ll i = 1 ; i <= n; i++)
        fac[i] = fac[i - 1] * i % p;
    return (fac[n] * modInverse(fac[r], p) % p *
            modInverse(fac[n - r], p) % p) % p;
}
// a+b=xor(a,b)+2*(a&b)//

bool isPrime(ll n){
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            return false;
        }
    }
    return true;
}


void solve()
{
    string s;
    cin>>s;
    ll cnt=0;
    ll n=s.size();
    for(int i=0;i<n;i++){
        cnt+=(s[i]-'0');
    }
    cout<<(cnt%9==0?"Yes":"No")<<endl;
}


int main()
{
	fio;
// 	#ifndef ONLINE_JUDGE
//     // for getting input from input.txt
//     freopen("input.txt", "r", stdin);
//     // for writing output to output.txt
//     freopen("output.txt", "w", stdout);
// 	#endif
 

	ll t=1;
// 	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

Measured memory_bytes: 3696
/*
[ ( ^ _ ^ ) ]
*/

// problem: atc/abc163_a

import java.io.*;
import java.util.*;


public class Main {
    int INF = (int)1e9;
    long MOD = 1000000007;


    void solve(InputReader in, PrintWriter out) throws IOException {
        int r = in.nextInt();
        out.println(2.0 * r * Math.PI);
    }
    

    public static void main(String[] args) throws IOException {
        InputReader in = new InputReader();
        PrintWriter out = new PrintWriter(System.out);
        int t = 1;//in.nextInt();
        while(t-- >0) {
            new Main().solve(in, out);
        }
        out.close();
    }
    
    public static void show(Object... o) {
        System.out.println(Arrays.deepToString(o));
    }
    
    static class InputReader {
        static BufferedReader br;
        static StringTokenizer st;
        public InputReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() { return Integer.parseInt(next()); }
        long nextLong() { return Long.parseLong(next()); }
        double nextDouble() { return Double.parseDouble(next()); }
    }
}

Measured memory_bytes: 33120
if __name__ == '__main__':
    a, b, c = map(int, input().split())
    k = int(input())

    count = 0
    while count < k:
        if a < b and b < c:
            break
        if not a < b:
            b *= 2
        elif not b < c:
            c *= 2
        count += 1

    if a < b and b < c:
        print("Yes")
    else:
        print("No")


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

#define mem( arr, i ) fill( arr, arr + sizeof (arr), i )
#define MEM( arr, i ) memset( arr, i, sizeof (arr) )
#define Push push_back
#define Pair make_pair
typedef unsigned long long ull;
typedef long long lli;
typedef pair<int,int> pii;
typedef pair<lli,lli> pll;
typedef vector<int> vcI;
typedef vector<lli> vcL;
typedef vector<pii> vPI;
typedef vector<pll> vPL;
//typedef priority_queue<T> prior_S<T>;
//typedef priority_queue< T, vector<T>, greater<T> > prior_B<T>;
const double PI = 3.141592653589793;
const lli I_MAX = 1LL << 60;
const lli mod = 1000000007;


void precal() {

	return;
}

void solve() {
	int len, n;
	string s;
	cin >> len >> n >> s;
	
	s[ n-1 ] += 32;
	
	cout << s << '\n';
}

int main() {
	precal();
	int t = 1;
//	cin >> t;
	for (int i = 1; i <= t; ++i) {
//		printf("Case #%d: ", i );
		solve();
	}
	return 0;
}



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

using namespace std;

int main(){
	string s;
	cin>>s;
	vector<int> freq(26,0);
	for(auto x:s){
		freq[x-'A']++;
	}
	for(int i=0;i<26;i++){
		if(freq[i]==2 || freq[i]==0){
			continue;
		}
		printf("No\n");
		return 0;
	}
	printf("Yes\n");
	return 0;
}

Measured memory_bytes: 256
n = int(input())
A = [int(i) for i in input().split()]
input()
M = [int(i) for i in input().split()]

def solve(i, m):
    if m == 0:
        return True
    if i >= n or m < 0:
        return False
    res = solve(i+1, m) or solve(i+1, m-A[i])
    return res

for m in M:
    if sum(A) < m:
        print("no")
    elif solve(0, m):
        print('yes')
    else:
        print('no')


Measured memory_bytes: 5628
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))

if sum(a)<sum(b):
    print(-1)
    exit()

c=[]
ans=0
count=0
for i in range(n):
    c.append(a[i]-b[i])
    if c[i]<0:
        ans+=1
        count+=c[i]
#print(count)
c.sort(reverse=True)
#print(ans)
i=0
while count<0:
    count+=c[i]
    ans+=1
    i+=1
    #print("DFGH")

print(ans)

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

#ifdef LOCAL
#define debug(var) cerr << (#var) << " = " << (var) << endl;
#else
#define debug(var)
#endif

void init() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
}

const int N = 1e3+23;

vector<long long> v;
long long a[N];
int skip[N*N], cnt[52];

void solve() {
  int n, k; scanf("%d%d", &n, &k);
  for (int i = 0; i < n; ++i) {
    scanf("%lld", a+i);
    if (i) a[i] += a[i-1];
  }
  for (int i = 0; i < n; ++i) {
    for (int j = i; j < n; ++j) {
      v.push_back(a[j]);
      if (i) v.back() -= a[i-1];
    }
  }
  long long ans = 0;
  for (int i = 50; i >= 0; --i) {
    long long b = 1LL << i;
    int cnt = 0;
    for (int j = 0; j < (int)v.size(); ++j) {
      if (skip[j]) continue;
      if (v[j] & b) ++cnt;
    }
    if (cnt < k) continue;
    ans |= b;
    for (int j = 0; j < (int)v.size(); ++j) {
      if (v[j] & b) continue;
      skip[j] = 1;
    }
  }
  printf("%lld", ans);
}

int main() {
  int t = 1; //scanf("%d", &t);
  while (t--) {
    solve();
  }
  return 0;
}


Measured memory_bytes: 9240
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>


using namespace std;

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;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 REPO(i, n) for(int i = 1;i <= n;i++)
#define ll long long
#define INF 1999999999
#define MINF -1999999999
#define INF64 1999999999999999999
#define ALL(n) n.begin(),n.end()
#define MOD 1000000007


ll n, s[114514],ans = 0, cnt = 0;
int main() {
	cin >> n;
	REPO(i, n)cin >> s[i];
	REPO(i, n + 1) {
		if (i == s[i])cnt++;
		else if (cnt > 0) {
			ans += max(1ll, (cnt + 1) / 2);
			cnt = 0;
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 1024
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	private enum COLOR {WHITE,GRAY,BLACK};
	private static final int INFINITY = 1 << 30;
	
	public static void main(String[] args) throws IOException {
		new Main().run();
	}
	
	private void run() throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(reader.readLine());
		int[][] m = new int[n][n];
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(reader.readLine());
			for (int j = 0; j < n; j++) {
				m[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		reader.close();
		System.out.println(prim(n, m));
	}

	private int prim(int n, int[][] m) {
		
		COLOR[] colors = new COLOR[n];
		int[] d = new int[n];
		int[] p = new int[n];
		for (int i = 0; i < n; i++) {
			colors[i] = COLOR.WHITE;
			d[i] = INFINITY;
			p[i] = -1;
		}
		
		d[0] = 0;
		while (true) {
			int minv = INFINITY;
			int u = -1;
			for (int i = 0; i < n; i++) {
				if (colors[i] == COLOR.BLACK) continue;
				if (minv > d[i]) {
					minv = d[i];
					u = i;
				}
			}
			if (u == -1) break;
			colors[u] = COLOR.BLACK;
			for (int v = 0; v < n; v++) {
				if (colors[v] == COLOR.BLACK) continue;
				if (m[u][v] == -1) continue;
				if (d[v] > m[u][v]) {
					d[v] = m[u][v];
					p[v] = u;
				}
			}
		}
		int cost = 0;
		for (int i = 0; i < n; i++) {
			if (p[i] != -1) cost += m[i][p[i]];
		}
		return cost;
	}
}


Measured memory_bytes: 27264
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
	
	public static void maxHeapify(int[] A, int i, final int H){
		int l = i * 2 + 1;
		int r = i * 2 + 2;
		
		int largest = -1;
		
		if(l < H && A[l] > A[i]){
			largest = l;
		}else{
			largest = i;
		}
		
		if(r < H && A[r] > A[largest]){
			largest = r;
		}
		
		if(largest != i){
			int tmp = A[i];
			A[i] = A[largest];
			A[largest] = tmp;
			
			maxHeapify(A, largest, H);
		}
	}
	
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		
		final int n = sc.nextInt();
		int[] heap = new int[n];
		for(int i = 0; i < n; i++){
			heap[i] = sc.nextInt();
		}
		
		for(int i = n / 2; i >= 0; i--){
			maxHeapify(heap, i, n);
		}
		
		for(int i = 0; i < n; i++){
			System.out.print(" " + heap[i]);
		}
		System.out.println();
		
	}

	public static class Scanner {
		private BufferedReader br;
		private StringTokenizer tok;

		public Scanner(InputStream is) throws IOException {
			br = new BufferedReader(new InputStreamReader(is));
		}

		private void getLine() throws IOException {
			while (!hasNext()) {
				tok = new StringTokenizer(br.readLine());
			}
		}

		private boolean hasNext() {
			return tok != null && tok.hasMoreTokens();
		}

		public String next() throws IOException {
			getLine();
			return tok.nextToken();
		}

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

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

		public void close() throws IOException {
			br.close();
		}
	}

}

Measured memory_bytes: 104752
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n, k; cin >> n >> k;
  vector<double> e(n);
  for(int i=0; i<n; i++){
    double p; cin >> p;
    e[i] = (p+1)/2;
  }
  
  double mx,sum_e;
  for(int i=0; i<k; i++){
    sum_e += e[i];
  }
  
  mx = sum_e;
  
  for(int i=0; i<n-k; i++){
    sum_e = sum_e - e[i] + e[i+k];
    if(sum_e > mx) mx = sum_e;
  }
  
  cout << fixed << setprecision(5) << mx << endl;
}

Measured memory_bytes: 1792
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		long N = sc.nextLong();
		
		long min = Long.MAX_VALUE;
		for (int i = 0; i < 5; i++) {
			min = Math.min(min, sc.nextLong());
		}
		
		System.out.println((N / min) + 5L - (min == 1 ? 1 : 0));
	}
}


Measured memory_bytes: 21844
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskB solver = new TaskB();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskB {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            long[] a = new long[n];
            for (int i = 0; i < n; ++i) a[i] = in.nextLong();
            long res = 0;
            long rem = 0;
            for (long x : a) {
                long y = x;
                x += rem;
                res += x / 2;
                rem = x % 2;
                if (y == 0) rem = 0;
            }
            out.println(res);
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

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

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

    }
}



Measured memory_bytes: 20924
#include<bits/stdc++.h>
using namespace std;
#define ms(x,y) memset(x, y, sizeof(x))
#define lowbit(x) ((x)&(-x))
#define sqr(x) ((x)*(x))
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;


void run_case() {
    int n, p;
    LL ans = 0;
    string s;
    cin >> n >> p >> s;
    if(p == 2) {
        for(int i = 0; i < n; ++i)
            if((s[i]-'0')%2==0) ans += i+1;
    } else if(p == 5) {
        for(int i = 0; i < n; ++i)
            if((s[i]-'0')%5==0) ans += i+1;
    } else {
        map<int, int> store;
        store[0]++;
        int idx = 1, now = 0;
        for(int i = n-1; i >= 0; --i) {
            now = (now + (s[i] - '0') * idx) % p;
            ans += store[now]++;
            idx = idx * 10 % p;
        }
    }
    cout << ans;
}


int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cout.flags(ios::fixed);cout.precision(9);
    //int t; cin >> t;
    //while(t--)
    run_case();
    cout.flush();
    return 0;
}

Measured memory_bytes: 916
h,w=map(int,input().split())
S=[["."]*(w+2)]+[["."]+list(input())+["."] for _ in range(h)]+[["."]*(w+2)]
ans="Yes"
for i in range(1,h+1):
  for j in range(1,w+1):
    if S[i][j]=="#" and S[i+1][j]=="." and S[i-1][j]=="." and S[i][j+1]=="." and S[i][j-1]==".":
      ans="No"
      break
print(ans)

Measured memory_bytes: 3064
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <sstream>
#include <unordered_map>
#include <vector>


#define INF 4000000000000000000LL
#define MOD 1000000007
#define ALL(x) std::begin(x), std::end(x)
#define RALL(x) (x).rbegin(), (x).rend()


long long compute(std::deque<int> deque)
{
  long long s = 0;

  int l, r, dl, dr;

  l = r = deque.front(); deque.pop_front();

  std::deque<int> a;

  a.push_back(l);
  
  while (! deque.empty()) {
    int m = deque.front(), p = deque.back(), d, dp = 0, ip = 0;

    if ((d = std::abs(l - m)) > dp) {
      dp = d;
      ip = 0;
    }
    if ((d = std::abs(l - p)) > dp) {
      dp = d;
      ip = 1;
    }
    if ((d = std::abs(r - m)) > dp) {
      dp = d;
      ip = 2;
    }
    if ((d = std::abs(r - p)) > dp) {
      dp = d;
      ip = 3;
    }

    s += dp;

    if (ip % 2 == 0) {
      deque.pop_front();

      if (ip < 2) {
        l = m;
        a.push_front(m);
      }
      else {
        r = m;
        a.push_back(m);
      }
    }
    else {
      deque.pop_back();

      if (ip < 2) {
        l = p;
        a.push_front(p);
      }
      else {
        r = p;
        a.push_back(p);
      }
    }
  }

  return s;
}


int main(int argc, char** argv)
{
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(0);

  std::cout << std::fixed << std::setprecision(6);
  std::cerr << std::fixed << std::setprecision(6);

  int N;

  std::cin >> N;

  std::vector<int> A(N);

  for (auto& i : A)
    std::cin >> i;

  std::sort(ALL(A));

  std::deque<int> deque1(ALL(A)), deque2(RALL(A));

  long long x = std::max(compute(deque1), compute(deque2));

  std::cout << x << std::endl;

  return 0;
}


Measured memory_bytes: 1952
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AtCoder
{
    class Program
    {
        static void Main()
        {
            var n = ReadIntArray();
            int r = n[0];
            int d = n[1];
            int x = n[2];

            for (int i = 0; i < 10; i++)
            {
                x = r * x - d;
                Console.WriteLine(x);
            }
        }

//ここからテンプレート
        //1行に1入力
        private static string ReadString() { return Console.ReadLine(); }
        private static int ReadInt() { return int.Parse(ReadString()); }
        private static long ReadLong() { return long.Parse(ReadString()); }
        private static double ReadDouble() { return double.Parse(ReadString()); }
        //1行に複数入力(配列で取得)
        private static string[] ReadStringArray() { return ReadString().Split(new[] { ' ' }, System.StringSplitOptions.RemoveEmptyEntries); }
        private static int[] ReadIntArray() { return ReadStringArray().Select(int.Parse).ToArray(); }
        private static long[] ReadLongArray() { return ReadStringArray().Select(long.Parse).ToArray(); }
        private static double[] ReadDoubleArray() { return ReadStringArray().Select(double.Parse).ToArray(); }
    }
}


Measured memory_bytes: 13268
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); i++)
#define per(i,n) for(int i = n-1; i >= 0; i--)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<long long, long long> Pll;
typedef vector<int> vi;
typedef vector<ll> vll;

int main() {
  ll d, g;
  cin >> d >> g;
  g /= 100;
  vll p(d);
  vll c(d);
  rep(i,d) {
    cin >> p[i] >> c[i];
    c[i] /= 100;
  }
  vll ans;
  rep(i,1<<d) {
    ll sum = 0;
    ll cnt = 0;
    rep(j,d) {
      if(i>>j&1) {
        sum += (j+1)*p[j];
        sum += c[j];
        cnt += p[j];
      }
    }
    if(sum>=g) ans.push_back(cnt);
    per(j,d) {
      if(!(i>>j&1)) {
        rep(k,p[j]-1) {
          sum += (j+1);
          cnt++;
          if(sum>=g) ans.push_back(cnt);
        }
      }
    }
  }
  sort(ans.begin(),ans.end());
  cout << ans[0] << endl;
  return 0;
}

Measured memory_bytes: 5872
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
import heapq
INF = float("inf")
MOD = 10**9 + 7
sys.setrecursionlimit(10**7)
# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W
def mi(): return map(int, input().split())
def ii(): return int(input())
###template###

S = input()
N = len(S)

if 'keyence' in S:
  print('YES')
  exit()

for l_omit in range(N+1):
  for r_omit in range(l_omit, N+1):
    if S[0:l_omit] + S[r_omit:N] == 'keyence':
      print('YES')
      exit()

print('NO')


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

int main() {
  vector<int> ls(5);
  for(int i = 0; i < 5; ++i) {
    cin >> ls[i];
  }
  int k;
  cin >> k;
  for(int i = 0; i < 4; ++i) {
    for(int j = 1; j < 5; ++j) {
      if(ls[j] - ls[i] > k) {
        cout << ":(" << endl;
        return 0;
      }
    }
  }
  cout << "Yay!" << endl;
  return 0;
}

Measured memory_bytes: 256