akhauriyash/Code-Regression huggingface dataset:
def main():
    n = int(input().strip())
    s = list(input().strip())

    bit = [[0] * 26 for _ in range(n + 1)]

    def query(i):
        result = [0] * 26
        while i:
            for j, x in enumerate(bit[i]):
                result[j] += x
            i -= i & -i
        return result
    
    def update(i, c, val):
        j = ord(c) - ord("a")
        while i < len(bit):
            bit[i][j] += val
            i += i & -i

    for i, c in enumerate(s, 1):
        update(i, c, 1)

    q = int(input().strip())
    for _ in range(q):
        Q = input().strip().split()
        if Q[0] == "1":
            i, c = int(Q[1]), Q[2]
            update(i, s[i - 1], -1)
            update(i, c, 1)
            s[i - 1] = c
        else:
            l, r = int(Q[1]), int(Q[2])
            cnt = [x - y for x, y in zip(query(r), query(l - 1))]
            print(sum(x > 0 for x in cnt))


main()


Measured memory_bytes: 210972
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<lint, int> pi;
const int MAXN = 200005;

struct disj{
	int pa[MAXN];
	int find(int x){
		return pa[x] = (pa[x] == x ? x : find(pa[x]));
	}
	void init(int n){
		iota(pa, pa + n + 1, 0);
	}
	bool uni(int p, int q){
		p = find(p);
		q = find(q);
		if(p == q) return 0;
		pa[q] = p; return 1;
	}
}disj;

struct edg{
	int s, e, x;
	bool operator<(const edg &e)const{
		return x < e.x;
	}
};

vector<edg> v;
int n, m, k, c[MAXN];

int main(){
	scanf("%d %d %d",&n,&m,&k);
	int cnt = k - 1;
	for(int i=1; i<=n; i++){
		scanf("%d",&c[i]);
		if(c[i]) cnt++;
		if(c[i]) v.push_back({i, c[i] + n, 0});
	}
	for(int i=1; i<=m; i++){
		int s, e, x;
		scanf("%d %d %d",&s,&e,&x);
		v.push_back({s, e, x});
	}
	sort(v.begin(), v.end());
	disj.init(n+k);
	lint ans = 0;
	for(auto &i : v){
		if(disj.uni(i.s, i.e)){
			ans += i.x;
			cnt--;
			if(cnt == 0) break;
		}
	}
	if(cnt > 0) ans = -1;
	cout << ans << endl;
}


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

int main() {
  int A,B,C,D;
  cin >> A>>B>>C>>D;
  
  int L = A + B;
  int R = C + D;
  
  if( L == R)
    cout << "Balanced" << endl;
  if( L > R)
    cout << "Left" << endl;
  if( L < R )
    cout << "Right"<< endl;
  
  
}

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


int main(){
	int N;cin >> N;
	vector<double> v(N);
	rep(i,N) cin >> v[i];
	sort(v.begin(),v.end());
	double sum = v[0];
	rep(i,N-1){
		sum = (sum + v[i+1])/2;
	}
	printf("%.10lf\n",sum);

}














Measured memory_bytes: 3736
import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")
al = "abcdefghijklmnopqrstuvwxyz"
AL = al.upper()

s = deque(X())
n = k()
normal = 0
for i in range(n):
  a = input().split()
  if int(a[0]) == 1:
    normal ^= 1
  else:
    k = int(a[1]) - 1
    k ^= normal
    if k == 1:
      s.append(a[2])
    else:
      s.appendleft(a[2])
print(''.join(s) if normal == 0 else ''.join(list(s)[::-1]))      


Measured memory_bytes: 16812
#include <iostream>
#include<cmath>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
    cin.tie(0);
    cin.sync_with_stdio(0);
    int n,x;   cin>>n>>x;
    if(x>=n) cout<<"unsafe";
    else cout<<"safe";
}


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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

void Main() {
    int N, K;
    cin >> N >> K;
    vector<double> A(N);
    rep(i, N) cin >> A[i];
    vector<double> cnt;
    rep(i, N) {
        double a = A[i];
        double s = ((a + 1) * a) / 2.0;
        cnt.push_back(s/a);
    }

    double ans = 0;
    int idx = 0;
    double S = 0;
    rep(i, N) {
        if (i - idx < K) {
            S+=cnt[i];
        }else{
            S-=cnt[idx];
            S+=cnt[i];
            idx++;
        }
        ans = max(ans, S);
    }
    cout << ans << '\n';
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 4980
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <iomanip>
#include <cstdio>
using namespace std;

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...) 42
#endif

#define SINV(t) greater<t>()
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REP2(i,n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
#define ALL(x) (x).begin(),(x).end()

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; }

typedef long long ll;
#define vv(t) vector<t>

template<typename T>
void SV(vector<T> v){
    REP(i,v.size()){
        #ifdef LOCAL
            cout << i << " : " << v[i] << endl;
        #endif
    }
}

int bitCount(int bits) {
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >> 16);
}


int main(){
    int A,B,C;
    cin >> A >> B >> C;
    printf("%d %d %d\n", C, A, B);
    return 0;
}


Measured memory_bytes: 256
using System;
using System.Text;
using System.Collections.Generic;
using System.Linq;
class Solve{
    public Solve(){}
    StringBuilder sb;
    public static int Main(){
        new Solve().Run();
        return 0;
    }
    void Run(){
        sb = new StringBuilder();
        Calc();
        Console.Write(sb.ToString());
    }
    void Calc(){
        string[] str = Console.ReadLine().Split(' ');
        int N = int.Parse(str[0]);
        int A = int.Parse(str[1]);
        int B = int.Parse(str[2]);
        str = Console.ReadLine().Split(' ');
        long[] V = new long[N];
        for(int i=0;i<N;i++){
            V[i] = long.Parse(str[i]);
        }
        Array.Sort(V);
        long sum = 0;
        for(int i=N-1;i>=N-A;i--){
            sum += V[i];
        }
        sb.Append(((double)(sum))/A+"\n");
        long count = 0;
        int p = N-A;
        while(p > 0 && V[p] == V[p-1]){
            p--;
        }
        int q = N-A;
        while(q < N-1 && V[q] == V[q+1]){
            q++;
        }
        if(q != N-1){
            count += GetConv(q-p+1,q-N+A+1); 
        }
        else{
            for(int i=A;i<=Math.Min(B,N-p);i++){
                count += GetConv(N-p,i);
            }
        }
        sb.Append(count+"\n");
    }
    long GetConv(int p,int q){
        long ans = 1;
        for(int i=0;i < p-q;i++){
            ans *= (p-i);
            ans /= (i+1);
        }
        return ans;
    }
}

Measured memory_bytes: 13396
[N,P]=[int(i) for i in input().split()]

ans=1

if(N==1):
	ans=P
else:
	i=2
	while(i*i<=P):	

		count=0
		
		while(P%i==0):
			P=P//i
			count+=1

		ans*=pow(i,count//N)

		i+=1

print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n;
int num[maxn];
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>num[i];
    int tmp = 0;
    vector<int> ans;
    for(int i=1;i<n;i++)
    {
        if(num[i]<=num[i-1])
        {
            tmp++;
        }
        else
        {
            ans.push_back(tmp);
            tmp = 0;
        }
    }
    ans.push_back(tmp);
    sort(ans.begin(),ans.end(),greater<int>());
    cout<<ans[0]<<endl;
}


Measured memory_bytes: 1276
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
a = Counter(LIST())
ans = len(a) if len(a) % 2 == 1 else len(a) - 1
print(ans)

Measured memory_bytes: 22748
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
int INF = (1LL << 30) - 1;
int MOD = 1e9+7;
main(){
    int N,K;
    cin >> N >> K;
    vector<int> V(N);
    rep(i,0,N)cin >> V[i];
    vector<ll> num;
    rep(i,0,N){
        ll sum = 0;
        rep(j,i,N){
            sum += V[j];
            num.push_back(sum);
        }
    }
    ll ans = 0;
    for(int i = 52;i >= 0;i--){
        int cnt = 0;
        for(auto j:num){
            if(j == -1)continue;
            //cout << j << " ";
            if(j & (1LL << i))cnt++;
        }
        //cout << endl;
        if(cnt < K)continue;
        //cout << i << endl;
        ans += 1LL << i;
        for(auto &j:num){
            if(!(j & (1LL << i))){
                j = -1;
            }
        }

    }
    cout << ans << endl;
}

Measured memory_bytes: 6388
/*
confirm 0LL and 1LL
confirm cornercases such as 0
confirm times of cin < 10^6
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using Pld = pair<ld, ld>;
using Vec = vector<ll>;
using VecP = vector<P>;
using VecB = vector<bool>;
using VecC = vector<char>;
using VecD = vector<double>;
using VecS = vector<string>;
using VecVec = vector<Vec>;
using Tree = vector<VecP>;
template <typename T>
using Vec1 = vector<T>;
template <typename T>
using Vec2 = vector<vector<T> >;
#define REP(i, m, n) for(ll (i) = (m); (i) < (n); ++(i))
#define REPN(i, m, n) for(ll (i) = (m); (i) <= (n); ++(i))
#define REPR(i, m, n) for(ll (i) = (m)-1; (i) >= (n); --(i))
#define REPNR(i, m, n) for(ll (i) = (m); (i) >= (n); --(i))
#define rep(i, n) REP(i, 0, n)
#define repn(i, n) REPN(i, 1, n)
#define repr(i, n) REPR(i, n, 0)
#define repnr(i, n) REPNR(i, n, 1)
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fs first
#define sc second
template <typename T>
bool chmax(T &a, const T& b){if(a < b){a = b; return true;} return false;}
template <typename T>
bool chmin(T &a, const T& b){if(a > b){a = b; return true;} return false;}
template <typename T>
void co(const T n){cout << n << endl;}
template <typename T>
void cosp(const T n){cout << n << ' ';}
void coVec(const Vec &v){for(ll i : v) cosp(i); cout << endl;}
void sonic(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);}
void setp(const ll n){cout << fixed << setprecision(n);}
const ll INF = 1e9+1;
const ll LINF = 1e18+1;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const ld PI = acos(-1);
const ld EPS = 1e-11;

int main(void){
	ll n, m;
	cin >> n >> m;
	Vec s(n), t(m);
	rep(i, n) cin >> s[i];
	rep(i, m) cin >> t[i];

	VecVec dp(n+1, Vec(m+1));
	dp[0][0] = 1;
	rep(i, n+1){
		rep(j, m+1){
			if(i) dp[i][j] += dp[i-1][j];
			if(j) dp[i][j] += dp[i][j-1];
			if(i && j && s[i-1] != t[j-1]) dp[i][j] -= dp[i-1][j-1];
			dp[i][j] += MOD;
			dp[i][j] %= MOD;
		}
	}
	co(dp[n][m]);

	return 0;
}


Measured memory_bytes: 31616
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef long double D;
typedef complex<D> P;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;

template<typename T,typename U>istream & operator >> (istream &i,pair<T,U> &A){i>>A.F>>A.S; return i;}
template<typename T>istream & operator >> (istream &i,vector<T> &A){for(auto &I:A){i>>I;} return i;}
template<typename T,typename U>ostream & operator << (ostream &o,const pair<T,U> &A){o<<A.F<<" "<<A.S; return o;}
template<typename T>ostream & operator << (ostream &o,const vector<T> &A){ll i=A.size(); for(auto &I:A){o<<I<<(--i?" ":"");} return o;}
template<typename T>vector<T> & cset(vector<T> &A,T e=T()){for(auto &I:A){I=e;} return A;}


int main(){
  ll n;
  cin>>n;
  vector<ll> A(n);
  cin>>A;
  vector<pair<bool,bool>> dp(n,{false,false});//-0,-1
  dp[0]={true,true};
  for(ll i=1;i<n;i++){
    if(dp[i-1].F && A[i-1]<=A[i]){dp[i].F=true;}
    if(dp[i-1].S && A[i-1]-1<=A[i]){dp[i].F=true;}
    if(dp[i-1].F && A[i-1]<=A[i]-1){dp[i].S=true;}
    if(dp[i-1].S && A[i-1]-1<=A[i]-1){dp[i].S=true;}
  }
  cout<<(dp.back().F || dp.back().S?"Yes":"No")<<endl;
  
  return 0;
}


Measured memory_bytes: 1280
{-# LANGUAGE FlexibleInstances    #-}
{-# LANGUAGE TypeSynonymInstances #-}

import           Control.Applicative
import           Control.DeepSeq
import           Control.Monad
import           Control.Monad.ST
import qualified Data.Array                    as A
import qualified Data.Array.IArray             as IA
import qualified Data.Array.IO                 as AI
import qualified Data.Array.MArray             as MA
import qualified Data.Array.ST                 as STA
import qualified Data.Array.Unboxed            as AU
import           Data.Bits
import qualified Data.ByteString.Char8         as BS
import           Data.Char
import qualified Data.Graph                    as G
import           Data.Int
import qualified Data.IntMap                   as IM
import qualified Data.IntSet                   as IS
import           Data.List
import qualified Data.Map.Strict               as M
import           Data.Maybe
import           Data.Ord
import qualified Data.Sequence                 as SQ
import qualified Data.Set                      as S
import           Data.Time
import qualified Data.Tree                     as T
import qualified Data.Vector                   as V
import qualified Data.Vector.Mutable           as VM
import qualified Data.Vector.Unboxed           as VU
import qualified Data.Vector.Unboxed.Mutable   as VUM

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

readInts :: Int -> IO [[Int]]
readInts n = replicateM n readInt

readInteger :: IO [Integer]
readInteger = map (fst . fromJust . BS.readInteger) . BS.words <$> BS.getLine

readIntegers :: Int -> IO [[Integer]]
readIntegers n = replicateM n readInteger

readString :: IO [String]
readString = map BS.unpack . BS.words <$> BS.getLine

readStrings :: Int -> IO [[String]]
readStrings n = replicateM n <$> readString

toPair :: [a] -> (a, a)
toPair [x, y] = (x, y)

count :: Eq a => a -> [a] -> Int
count a as = length $ filter (== a) as

put :: Show a => a -> IO ()
put = putStr . show

putList :: Show a => [a] -> IO ()
putList [n     ] = put n
putList (n : ns) = do
  put n
  putStr " "
  putList ns

putStrList :: [String] -> IO ()
putStrList [n     ] = putStr n
putStrList (n : ns) = do
  putStr n
  putStr " "
  putStrList ns

yesNoUpper b | b         = putStrLn "YES"
             | otherwise = putStrLn "NO"

yesNo b | b         = putStrLn "Yes"
        | otherwise = putStrLn "No"

main = do
  [a, b] <- readInt
  print $ ((a + b )`mod` 24)


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

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

  int n, x, t;
  cin >> n >> x >> t;
  cout << (n+x-1) / x * t << endl;
}

Measured memory_bytes: 3644
#include<stdio.h>
int main()
{
    int i, n, mul = 1, temp, num = 0, base, c = 0;

    scanf("%d %d", &n, &base);
    temp = n;
    while(temp)
    {
        num = num + (temp%base) * mul;
        mul = mul * 10;
        c++;
        temp = temp / base;
    }
    printf("%d\n", c);

    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
#define REP(i, n) for (int i = 0; (i64)(i) < (i64)(n); ++i)

#ifdef ENABLE_DEBUG
template <typename T>
void debug(T value) {
  cerr << value;
}
template <typename T, typename... Ts>
void debug(T value, Ts... args) {
  cerr << value << ", ";
  debug(args...);
}
#define DEBUG(...)                              \
  do {                                          \
    cerr << " \033[33m (L" << __LINE__ << ") "; \
    cerr << #__VA_ARGS__ << ":\033[0m ";        \
    debug(__VA_ARGS__);                         \
    cerr << endl;                               \
  } while (0)
#else
#define debug(...)
#define DEBUG(...)
#endif

bool is_753(i64 x) {
  bool has7 = false, has5 = false, has3 = false;
  while (x) {
    int d = x % 10;
    if (d == 7)
      has7 = true;
    else if (d == 5)
      has5 = true;
    else if (d == 3)
      has3 = true;
    else
      return false;
    x /= 10;
  }
  return has7 && has5 && has3;
}

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

  int cnt = 0;
  auto f = [&](auto rec, i64 base, i64 x) -> void {
    if (x > N) return;
    if (is_753(x)) ++cnt;
    for (i64 c : {7, 5, 3}) {
      rec(rec, base * 10, c * base + x);
    }
  };
  f(f, 1LL, 0LL);
  cout << cnt << endl;
}


Measured memory_bytes: 3664
import java.util.*;
import java.util.Collections;
import java.util.stream.Collectors;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int A = sc.nextInt();
    int B = sc.nextInt();
    int cnt = 0;
    for (int i = A; i <= B; i++) {
      String C = String.valueOf(i);
      String D = C.substring(0, 1);
      String E = C.substring(C.length() - 1, C.length());
      String F = C.substring(1, 2);
      String G = C.substring(C.length() - 2, C.length() - 1);
      if (D.equals(E) && F.equals(G)) {
        cnt++;
      }
    }
    System.out.println(cnt);
  }
}


Measured memory_bytes: 38868
#include <stdio.h>

int a = 0;
int b = 0;
int c = 0;
int yesorno = 0;

int main()
{
    scanf("%d %d %d", &a, &b, &c);

    if (a == b && b == c || a != b && b != c && a != c)
    {
        yesorno = 0;
    }
    else
    {
        yesorno = 1;
    }

    if (yesorno == 0)
    {
        printf("No\n");
    }
    else
    {
        printf("Yes\n");
    }

    return 0;
}

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

#define rep(i, a) for (int i = 0; i < (a); i++ )
#define FOR(i, m, n) for(int i = m; i < n; i++)
 
typedef pair<int,int> P;
typedef long long ll;
 
const int INF = 1001001001;
const int MOD = 1000000007;
const double PI=acos(-1);


int main(){
    string X;
    cin >> X;
    vector<char> A;

    rep(i,X.size()) {
        if (A.size()==0) {
            A.push_back(X[i]);
        }
        else {
            if (A.back()=='S' && X[i]=='T') {
                A.pop_back();
            }
            else {
                A.push_back(X[i]);
            }
        }
    }
    cout << A.size() << endl;
}    

Measured memory_bytes: 3736
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
import heapq
INF = 10**18

MAX_SILVER = 3000 

class Dijkstra:
    def __init__(self, adj):
        self.adj = adj
        self.dist = [INF] * len(adj)
        self.q = []

    def calc(self, start):
        self.dist[start] = 0
        heapq.heappush(self.q, (0, start))
        while len(self.q) != 0:
            prov_cost, src = heapq.heappop(self.q)
            if self.dist[src] < prov_cost:
                continue
            for dest, cost in self.adj[src]:
                if self.dist[dest] > self.dist[src] + cost:
                    self.dist[dest] = self.dist[src] + cost
                    heapq.heappush(self.q, (self.dist[dest], dest))
        return self.dist

n, m, s = map(int, input().split())
edge = [[] for _ in range(n * MAX_SILVER)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1; v -= 1
    for i in range(a, MAX_SILVER):
        edge[u*MAX_SILVER + i].append((v*MAX_SILVER + i-a, b))
        edge[v*MAX_SILVER + i].append((u*MAX_SILVER + i-a, b))

for v in range(n):
    c, d = map(int, input().split())
    for i in range(MAX_SILVER - 100):
        edge[v*MAX_SILVER + i].append((v*MAX_SILVER + i + c, d))

DIJK = Dijkstra(edge)
if s > 2500:
    s = 2500
dist = DIJK.calc(s)

for v in range(1, n): 
    ret = INF
    for val in range(MAX_SILVER):
        if dist[v*MAX_SILVER + val] < ret:
            ret = dist[v*MAX_SILVER + val]
    print(ret)

Measured memory_bytes: 121848
#include <bits/stdc++.h>
using namespace std;
using ll= long long;
using vi= vector<int>;
using vvi= vector<vi>;
using vd= vector<double>;
using vvd= vector<vd>;
using vc= vector<char>;
using vb= vector<bool>;
using vl= vector<ll>;
#define rep(i,x,n) for(int i=x; i<n; i++)
#define all(x) x.begin(), x.end()

int main(){
  bool all;
  int n,m,sw,ans=0;
  cin >> n >> m;
  vi k(m);
  vvi s(m,vi (n));
  vi p(m);
  rep(i,0,m){
    cin >> k[i];
    rep(j,0,k[i]){
      cin >> s[i][j];
    }
  }
  rep(i,0,m){
    cin >> p[i];
  }

  rep(bit,0,1<<n){
    all=true;
    rep(i,0,m){
      sw=0;
      rep(j,0,k[i]){
        if(bit>>(s[i][j]-1)&1){
          sw++;
        }
      }
      if(sw%2!=p[i]){
        all=false;
      }
    }
    if(all){
      ans++;
    }
  }
  cout << ans;
  
  return 0;
}


Measured memory_bytes: 256
import sys
def input():
    return sys.stdin.readline()[:-1]


N = int(input())

restaurants = []

for i in range(N):
    S, P = input().split()

    restaurants.append(
        {
            'S': S,
            'P': P,
            'number': i + 1
        }
    )

restaurants.sort(key=lambda x: (x['S'], -int(x['P'])))

for res in restaurants:
    print(res['number'])


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

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP0(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REP1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)

typedef long long LL;
typedef pair<int, int> pii;

const int INTINF = int(1e9) + 1;
const LL LLINF = LL(1e18) + 1;
long double eps = 1.0E-14;
#define pow10(n) int(1e##n + n)

void solve()
{
    int x1, y1;
    cin >> x1 >> y1;
    int x2, y2;
    cin >> x2 >> y2;

    cout << x2 - (y2 - y1) << " ";
    cout << y2 + (x2 - x1) << " ";
    cout << x1 - (y2 - y1) << " ";
    cout << y1 + (x2 - x1) << endl;
}

int main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(10);
    solve();
    return 0;
}


Measured memory_bytes: 256
n, y = map(int, input().split())

mx = y // 1000

for i in range(mx):
    for j in range(mx-i):
        if i * 10000 + j * 5000 + (n-i-j) * 1000 == y and n-i-j >= 0:
            print(i, j, n-i-j)
            exit()
else:
    print(-1, -1, -1)

Measured memory_bytes: 40684
#include <iostream>
#define lli long long int
using namespace std;

int main()
{
    lli a,b,h;
    cin>>a>>b>>h;
    if(a<b)
    {
        cout<<(a*h)+(h/2)*(b-a)<<endl;
    }
    else
    {
            cout<<(b*h)+(h/2)*(a-b)<<endl;
    }

    //cout << "Hello world!" << endl;
    return 0;
}


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

int main(){

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

    long long n, i;
    cin >> n;

    long long sq = sqrt(n), ans;
    for(i = sq; i >= 1; --i){
        if(n % i == 0) { ans = i; break; }
    }
    ans += (n / i);
    cout << ans - 2 << '\n';
    return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;
typedef long long ll;

ll sum_digits(ll n){
    ll ret = 0;
    for(; n > 0; n /= 10){
        ret += n % 10;
    }
    return ret;
}

int main(){
    ll n, a, b;
    cin >> n >> a >> b;
    ll ans = 0;
    for(ll i = 1; i <= n; ++i){
        ll s = sum_digits(i);
        if(s >= a && s <= b){
            ans += i;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    double a,b,n,m;
    cin>>n>>m;
    for(double i=1;i<=10000;i++)
    {
        a=i*.08;
        b=i*.1;
        a=(ll)a;
        b=(ll)b;
        if(a==n&&b==m)
        {
            cout<<(ll)i<<endl;
            return 0;
        }
    }
    cout<<-1<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n,k,d[102],res;
int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    scanf("%d %d",&n,&k);
    for(int i=0;i<k;i++){
        int r;
        scanf("%d",&r);
        for(int j=0;j<r;j++){
            int q;
            scanf("%d",&q);
            d[q]++;
        }
    }
    for(int i=1;i<=n;i++) if(!d[i]) res++;
    printf("%d",res);
    return 0;
}


Measured memory_bytes: 3820
n = int(input())
ls = [0,0,0,0]
for i in range(n):
    ans = str(input())
    if ans == "AC": ls[0] += 1 
    if ans == "WA": ls[1] += 1 
    if ans == "TLE": ls[2] += 1 
    if ans == "RE": ls[3] += 1 

print(f'''AC x {ls[0]}
WA x {ls[1]}
TLE x {ls[2]}
RE x {ls[3]}''')

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

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

	string S;

	cin>>S;
    string ans = "Yes";
    char c1,c2;
    if(S.length()%2==1){
        ans = "No";
    }else{
        rep(i,S.length()/2){
            c1 = S[i*2];
            c2 = S[i*2+1];
            if(c1!='h'||c2!='i'){
                ans = "No";
                break;
            }
        }
    }
    cout<<ans<<"\n";
	
	return 0;
}

Measured memory_bytes: 256
from sys import stdin
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(3)]
lin = []
for i in range(3):
    for j in range(3):
        lin.append(li[i][j])
n = int(stdin.readline().rstrip())
lis = [int(stdin.readline().rstrip()) for _ in range(n)]
liv = []
for i in lin:
    if i in lis:
        liv.append(0)
    else:
        liv.append(1)
if liv[0:3] == [0,0,0] or liv[3:6] == [0,0,0] or liv[6:9] == [0,0,0]:
    print("Yes")
    exit()

if liv[0] == 0 and liv[3] == 0 and liv[6] == 0:
    print("Yes")
    exit()
if liv[1] == 0 and liv[4] == 0 and liv[7] == 0:
    print("Yes")
    exit()
if liv[2] == 0 and liv[5] == 0 and liv[8] == 0:
    print("Yes")
    exit()


if liv[0] == 0 and liv[4] == 0 and liv[8] == 0:
    print("Yes")
    exit()
if liv[2] == 0 and liv[4] == 0 and liv[6] == 0:
    print("Yes")
    exit()
print("No")

Measured memory_bytes: 3064
// In the name of GOD
 
#include <bits/stdc++.h>
#define ll long long
#define pp pair <int, int>
using namespace std;
const int N = 2e5 + 10, MOD = 1e9 + 7;
const ll INF = 1e18;

void solve() {
	int n, k;
	cin >> n >> k;
	vector <int> a(n);
	for (int i = 0; i < n; ++i)
		cin >> a[i];
	vector <int> winner(k + 1, 2);

	for (int stones = 1; stones <= k; ++stones) {
		for (int j = 0; j < n; ++j) {
			if (a[j] > stones) continue;
			if (winner[stones -a[j]] == 2)
				winner[stones] = 1;
		}
	}
	cout << (winner[k] == 1 ? "First" : "Second");
}

int main () {
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
    int tt = 1;
    // cin >> tt;
    for (int tc = 1; tc <= tt; ++tc) {
        solve();
    }
}                                  

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define pb push_back
#define mp make_pair
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(),x.end()
#define mem0(s) memset(s,0,sizeof(s))
#define meminf(s) memset(s,0x3f,sizeof(s))
#define mp_insert(a,b,c) mp.insert(map<pair<int,int>,int>::value_type(make_pair(a,b),c))
double pi=acos(-1);
typedef long long ll;
typedef unsigned long long ull;
inline ll lowbit(ll x){return x&(-x);}
inline ll min(ll a,ll b){return a<b?a:b;}
inline ll max(ll a,ll b){return a>b?a:b;}
const int INF=0x3f3f3f3f,max_n=100005,mod=19260817;
inline ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
inline ll pow(ll a,ll b,ll mod){ll res=1;a%=mod;assert(b>=0);for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll a,b,x;
ll ans[10005];
int main()
{
    cin>>x;
    for(int i=120;i>=1;i--)
    {
    	ans[120-i+1]=pow(-i,5,(1LL<<(63-1)));
	}
	ans[121]=0;
	for(int i=122;i<=241;i++)
	{
		ans[i]=pow(i-121,5,(1LL<<(63-1)));
	}
	for(int i=1;i<=241;i++)
	{
		for(int j=1;j<=241;j++)
		{
			if(ans[i]-ans[j]==x)
			{
				cout<<i-121<<' '<<j-121<<endl;
				return 0;
			}
		}
	}
    return 0;
}

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pair<int, int> > vpii;
typedef vector<pair<ll, ll> > vpll;

#define pll pair<ll,ll>
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define F first
#define S second
#define rep(i,n) for (int i = 0; i < n; ++i) 
#define REP(i,k,n) for (int i = k; i <= n; ++i) 
#define REPR(i,k,n) for (int i = k; i >= n; --i)
#define pb push_back
#define watch(x) cout << (#x) << " is " << (x) << endl
#define sz(a) int((a).size())
#define endl '\n' // remove for interactive

const int INF = 1e9;
const ll mod = 1e9 + 7;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}



void solve()
{
    int cnt = 0;
    int flag = 0;
    int n; cin>>n;
    // int lastx, lasty;
    rep(i, n)
    {
        int x, y; cin>>x>>y;
        if(x == y) cnt++;
        else cnt = 0;
        if(cnt >= 3) flag = 1;
    }
    if(flag) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

int main()
{
    // clock_t start, end;
    // start = clock();
    ios_base::sync_with_stdio(0); //cant use scanf, printf
    cin.tie(0);cout.tie(0); // no longer auto flush cout before each cin, remove for interactive
    int t = 1;
    // cin>>t;
    REP(i, 1, t)
    {
        solve();
        
    }
    // end = clock();
    // double time_taken = double(end - start) / double(CLOCKS_PER_SEC); 
    // watch(time_taken);
    ll x = INF; x++;
    return 0;
    
}



/*before sub
TEST: 0(1 by 1 too), 1, equal, -ve, bounds(random and ez)
ERR/WA: loop vars, out of bounds, endl, finish taking inputs, large doubles, larger INF, corr mod, t, early/late mod
RE: double dec, integer overflow(ll or 1LL mult)
*/





Measured memory_bytes: 3648
"use strict"

const arg_str = require('fs').readFileSync('/dev/stdin', 'UTF-8')
const args = arg_str.split('\n')
const N = +args[0]
const S = args[1]

if(N < 2){
    console.log('No')
    return
}

if(S.substr(0, N/2) == S.substr(N/2)){
    console.log('Yes')
}else{
    console.log('No')
}


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

 int main() {
   int N,K;
   string S;
   cin >> N >> K;
   cin >> S;
   
   if(S.at(K-1) == 'A'){
     S.at(K-1) = 'a';
   }else if(S.at(K-1) == 'B'){
     S.at(K-1) = 'b';
   }else if(S.at(K-1) == 'C'){
     S.at(K-1) = 'c';
   }
   cout << S << endl;
}

Measured memory_bytes: 256
import java.util.*;
import static java.lang.System.*;

public class Main {

	Scanner sc = new Scanner(in);
	
	void run() {
		int n = sc.nextInt();
		int[] num = new int[10];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < 10; j++)
				num[j] = sc.nextInt();
			
			int a, b;
			boolean flag, flag2 = false;
			for (int j = 0; j < 1 <<10; j++) {
				a = b = 0;
				flag = true;
				for (int k = 0; k < 10; k++) {
					if ((1 & j >> k) == 1) {
						if (a < num[k]) {
							a = num[k];
						} else {
							flag = false;
							break;
						}
					} else {
						if (b < num[k]) {
							b = num[k];
						} else {
							flag = false;
							break;
						}
					}
				}
				if (flag) {
					flag2 = true;
					break;
				}
			}
			if (flag2)
				out.println("YES");
			else
				out.println("NO");
		}
	}
	
	public static void main(String[] args) {
		new Main().run();
	}

}

Measured memory_bytes: 19692
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define pll pair<ll,ll>
#define pii pair<int,int>
#define rep(i,n) for(int i=0;i<n;i++)
#define sz(x) ((ll)(x).size())
#define pb push_back
#define mp make_pair
#define bit(n) (1LL<<(n))
#define F first
#define S second
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const ll INF = 1LL<<60;
const ll mod = (int)1e9 + 7;

/*
テストケース全てに目を通す
テストケースが2個以下だったらなんかある
N最小のコーナーケースがないか調べる
制約をしっかりと確認する（1からNまでの順列、全て異なる値などの制約も含め）
操作の逆順を考える
Codeforcesではscanfを使う
エラー出力は消す
エラー出力を消せ！！！！！
 */

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    if(n%2==1){
        cout << "No";
        return 0;
    }
    rep(i,n/2){
        if(s[i]!=s[i+n/2]){
            cout << "No";
            return 0;
        }
    }
    cout << "Yes";
    return 0;
    


}

/*



 */



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <tuple>
#include <cmath>
#include <iomanip>
#include <map>
#include <cstring> //memset(dp,0,sizeof(dp))
#include <functional>
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define repp(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define ppb pop_back()
#define ALL(a) (a).begin(),(a).end()
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;

signed main(){
    int c[3][3];
    rep(i,3)rep(j,3)cin >> c[i][j];
    bool fl=1;
    if(c[1][0]-c[0][0]!=c[1][1]-c[0][1]||c[1][2]-c[0][2]!=c[1][1]-c[0][1])fl=0;
    if(c[2][0]-c[1][0]!=c[2][1]-c[1][1]||c[2][2]-c[1][2]!=c[2][1]-c[1][1])fl=0;
    if(c[0][1]-c[0][0]!=c[1][1]-c[1][0]||c[2][1]-c[2][0]!=c[1][1]-c[1][0])fl=0;
    if(c[0][2]-c[0][1]!=c[1][2]-c[1][1]||c[2][2]-c[2][1]!=c[1][2]-c[1][1])fl=0;
    if(fl)cout<<"Yes" << endl;
    else cout<<"No"<<endl;
}


Measured memory_bytes: 256
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
#define eps 1e-8
#define eq(x,y) (fabs((x)-(y)) < eps)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int>pii;
const ll mod = 998244353;
long double PI = acosl(-1);
const ll infl = 1e18;
const int inf = 2e9;
const int nmax = 1e5+5;
const int MAXLG = log2(nmax)+1;
//mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
//typedef tree< int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ost;

ll nxt[nmax];
ll n, x, m;
bool vis[nmax];

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

    cin>>n>>x>>m;
    for(ll i=0; i<m; i++){
        nxt[i] = (1LL*i*i)%m;
    }

    ll ans = 0;
    while(n--){
        if(vis[x]){
            n++;
//            cout<<"watff "<<endl;
            int luplen = 1;
            ll lupsam = x;
            int x1 = nxt[x];
            while(x1!=x){
                lupsam += x1, luplen += 1;
                x1 = nxt[x1];
//                cout<<"atka" <<endl;
            }
            ll taken = n / luplen;
            n %= luplen;
            ans += taken * lupsam;
            break;
        }
        ans += x;
        vis[x] = true;
        x = nxt[x];
//        cout<<"x = "<<x<<endl;
    }
//    cout<<n<<endl;
    for(int i=0; i<n; i++){
        ans += x;
        x = nxt[x];
//        cout<<"mane ki "<<endl;
//        cout<<n<<endl;
    }
    cout<<ans<<endl;


}
/*
*/


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

using namespace std;

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

#define fi first
#define se second
#define endl '\n'
#define MOD(n,k) ( (n % k) + k ) % k
#define isOn(S, j) (S & (1 << j) )
#define setBit(S, j) (S | (1 << j ) )
#define LSB(S) (S & (-S))

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

	cin >> n;
	cout << "ABC" << n << endl;

	return 0;
}


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

    
int main(){
    string s;
    cin >> s;
    bool out=true;
    for(int i=0;i<s.size();i++){
        int a=0;
        for(int l=0;l<s.size();l++){
            if(s.at(i)==s.at(l)){
                a++;
            }
        }
        if(a!=2){
            out=false;
            break;
            }
    }
    if(out){cout << "Yes" << endl;}
    else{cout << "No" << endl;}
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
	long long n;
	cin >> n;
	long long ans = n;
	for(long long i = 1; i*i <= n; i++)
	{
		if(n%i == 0)
		{
			ans = min(ans,(i-1)+((n/i) -1));
		}
	}
	cout << ans << endl;
}

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

using namespace std;

typedef long long lli;
typedef double lld;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<double> vdl;
typedef vector<vector<lli>> mat;
typedef vector<vdl> mad;
typedef unordered_map<lli,unordered_map<lli,lli>> graph;
typedef complex<double> cmp;
typedef vector<cmp> vcl;

lli n,m;
mat lr;

class bit {
private:
	vll* v;
	lli n;
public:
	bit (lli n) {
		this->v = new vll(n+1);
		this->n = n;
	}
	void add(lli i,lli val){
		for(;i <= n;i += i&-i) this->v->at(i) += val;
	}
	lli sum(lli i){
		lli ret = 0;
		for(;i > 0;i -= i&-i) ret += this->v->at(i);
		return ret;
	}
};


int main(){
  cin >> n >> m;
  lr = mat(n);
  for(lli i = 0;i < n;i++){
    lli l,r;
    cin >> l >> r;
    lli d = r-l+1;
    lr[i] = vll({d,l,r});
  }
  sort(lr.begin(),lr.end());
  bit bt = bit(m+1);
  for(lli d = 1,i = 0;d <= m;d++){
    while(i < n && lr[i][0] <= d){
      bt.add(lr[i][1],1);
      bt.add(lr[i][2]+1,-1);
      i++;
    }
    lli ans = n-i;
    for(lli i = d;i <= m;i += d){
      ans += bt.sum(i);
    }
    cout << ans << endl;
  }
  return 0;
}


Measured memory_bytes: 18176
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <set>
#include <unordered_map>
#include <queue>
#include <stack>
#include <cmath>
#include <functional>
#include <deque>
#include <bitset>
#include <climits>
#include <cstdio>
#include <list>
#include <iomanip>
using namespace std;

#define ll long long int
#define mp make_pair
#define pb push_back
#define fi first
#define si second
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define F(a,n) for(int i=0;i<n;i++){cin>>a[i];}
#define F1(a,n) for(int i=1;i<=n;i++){cin>>a[i];}
#define P(a,n) for(int i=0;i<n;i++){cout<<a[i]<<' ';}cout<<endl;
#define P1(a,n) for(int i=1;i<=n;i++){cout<<a[i]<<' ';}cout<<endl;
#define NF(a,n,m) for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>a[i][j];}}
#define NF1(a,n,m) for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];}}
#define PNF(a,n,m) for(int i=0;i<n;i++){for(int j=0;j<m;j++){cout<<a[i][j]<<' ';}cout<<endl;}cout<<endl;
#define PNF1(a,n,m) for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cout<<a[i][j]<<' ';}cout<<endl;}cout<<endl;
#define AS 200001
#define mod 1000000007
int solve(vector<int>&v, int n, int k) {
	ll dp[n + 2][k + 2];
	for (int j = 0; j <= k; j++) {
		dp[1][j] = (j > v[1]) ? 0 : 1;
	}
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= k; j++) {
			if (j == 0)
				dp[i][j] = dp[i - 1][j];
			else
				dp[i][j] = (mod + dp[i][j - 1] + dp[i - 1][j] - ((j - v[i] - 1 >= 0) ? dp[i - 1][j - v[i] - 1] : 0)) % mod;
		}
	}
	return dp[n][k];
}
int main() {
	fastIO
	int  n, k;
	cin >> n >> k;
	vector<int>v(n + 1);
	F1(v, n);
	cout << solve(v, n, k);
}

Measured memory_bytes: 78336
#!/usr/bin/env python3
x, y = map(int, input().split())
c = 0
if x * y < 0:
    x = abs(x)
    y = abs(y)
    c = 1

if y < x:
    print(1 + (y != 0 and x != 0) + x - y - c)
else:
    print(y - x + c)


Measured memory_bytes: 9160
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)
var out = bufio.NewWriter(os.Stdout)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	a, _ := strconv.Atoi(next())
	return a
}

const DIV uint64 = 1e9 + 7

func pow(a uint64, n int) uint64 {
	if n == 0 {
		return 1
	} else if n%2 == 0 {
		p := pow(a, n/2)
		return p * p % DIV
	} else {
		p := pow(a, n/2)
		return a * p * p % DIV
	}
}

func main() {
	buf := make([]byte, 1024*1024)
	sc.Buffer(buf, bufio.MaxScanTokenSize)
	sc.Split(bufio.ScanWords)
	defer out.Flush()

	N := nextInt()
	ans := (2*DIV + pow(10, N) - 2*pow(9, N) + pow(8, N)) % DIV
	fmt.Fprintf(out, "%d\n", ans)
}


Measured memory_bytes: 1808
#!usr/bin/env python3

import sys


# def generate_buidlings(building, floor, room):
#     empty_buildings = {
#             key: [[0 for col in range(room)] for row in range(floor)]
#             for key in range(1, building+1)
#     }
#     return empty_buildings
#
#
# def occupy_buildings(empty_buildings):
#     occupied_buildings = generate_buidlings(4, 3, 10)
#     n = int(sys.stdin.readline())
#
#     for i in range(n):
#         lst = [int(num) for num in sys.stdin.readline().split()]
#         occupied_buildings[lst[0]][lst[1]-1][lst[2]-1] += lst[3]
#
#     return occupied_buildings

def generate_buidlings_with_residents(building, floor, room):
    buildings = {
            key: [[0 for col in range(room)] for row in range(floor)]
            for key in range(1, building+1)
    }

    n = int(sys.stdin.readline())
    for i in range(n):
        lst = [int(num) for num in sys.stdin.readline().split()]
        buildings[lst[0]][lst[1]-1][lst[2]-1] += lst[3]

    return buildings


def print_buildings():
    separator = '####################'
    buildings_with_residents = generate_buidlings_with_residents(4, 3, 10)

    for idx, (key, value) in enumerate(buildings_with_residents.items()):
        for floor in value:
            print(' %s %s %s %s %s %s %s %s %s %s' % tuple(floor))
        if key < len(buildings_with_residents):
            print(separator)


def main():
    print_buildings()


if __name__ == '__main__':
    main()

Measured memory_bytes: 7788
#include <bits/stdc++.h>
using namespace std;
int main() {
  int X,Y,Z;
  cin >> X;
  Y = X;
  Z = 0;
  for(int i = 0; i < 9; i++){
  	Z += X % 10;
  	X /= 10;
    if(X == 0){
      break;
    }
  }
  if(Y % Z == 0){
  	cout << "Yes" << endl;
  }else{
  	cout << "No" << endl;
  }
}

Measured memory_bytes: 256
h, w = [int(v) for v in input().split()]
a = []
for i in range(h):
    row = input()
    if '#' in row:
        a.append(list(row))

remove_column = []
for j in range(w):
    if len([True for v in a if v[j] == '#']) == 0:
        remove_column.append(j)
remove_column = remove_column[::-1]

for j in remove_column:
    for i in range(len(a)):
        a[i].pop(j)

for line in a:
    print(''.join(line))

Measured memory_bytes: 3188
#define _USE_MATH_DEFINES

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <unordered_map> 
#include <unordered_set>
#include <functional>

using namespace std;

typedef pair<long long int, long long int> P;
typedef tuple<int, int, int> T;

long long int INF = 1e18;
long long int MOD = 1e9 + 7;

#define MAX_V 300

int N;
string S[210];
int odd[210];

bool func(int pos, bool input){
	if(odd[pos] != -1){
		return odd[pos] == input;
	}
	odd[pos] = input;
	bool ret = true;
	for(int i = 0; i < N; i++){
		if(S[i][pos] == '1'){
			ret = (ret && func(i, !input));
		}
	}
	return ret;
}


long long int cost[MAX_V][MAX_V];
bool used[MAX_V];
long long int d[MAX_V];

// O(V^2)

void shortest_path(int s){
	for(int i = 0; i < N; i++){
		d[i] = INF;
		used[i] = false;
	}
	d[s] = 0;
	while(true){
		
		int add_v = -1;
		
		for(int u = 0; u < N; u++){
			if(!used[u] && (add_v == -1 || d[u] < d[add_v])){
				add_v = u;
			}
		} //
		
		if(add_v == -1){
			break;
		} //
		used[add_v] = true;
		
		for(int u = 0; u < N; u++){
			d[u] = min(d[u], d[add_v] + cost[add_v][u]);
		} //
	}
}


int main(){
	cin >> N;
	for(int i = 0; i < N; i++){
		cin >> S[i];
	}
	for(int i = 0; i < N; i++){
		odd[i] = -1;
	}
	bool ret = func(0, true);
	if(!ret){
		cout << -1 << endl;
		return 0;
	}
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			if(S[i][j] == '1'){
				cost[i][j] = 1;
			}else{
				cost[i][j] = INF;
			}
		}
	}
	long long int ans = 0;
	for(int i = 0; i < N; i++){
		shortest_path(i);
		for(int j = 0; j < N; j++){
			ans = max(ans, d[j]);
		}
	}
	cout << ans + 1 << endl;
	return 0;
}

Measured memory_bytes: 768
#include <iostream>
#include <vector>
#include <algorithm>
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define REP(i, n) for(int i = 1; i < (int)(n); ++i)
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    vector<vector<char>> A(N, vector<char>(N)), B(M, vector<char>(M));
    rep(i, N) rep(j, N) cin >> A[i][j];
    rep(i, M) rep(j, M) cin >> B[i][j];
    
    for (int i = 0; i + M <= N; ++i) for (int j = 0; j + M <= N; ++j) {
        bool judge = true;
        rep(k, M) rep(l, M) {
            if (A[i + k][j + l] != B[k][l]) judge = false;
        }
        if (judge) {
            cout << "Yes\n";
            return 0;
        }
    }
    cout << "No\n";
    return 0;
}


Measured memory_bytes: 3644
#include<cstdio>
using namespace std;
int n,K;
long long cnt,t;
long long ans=0ll;
int main()
{
	scanf("%d%d",&n,&K);
	if (K%2==0)
	{
		K/=2;
		cnt=n/K;
		if (cnt%2==0) { cnt/=2; t=cnt; }
		else { cnt=cnt/2+1; t=n/K-cnt; }
		ans=cnt*cnt*cnt+t*t*t;
		printf("%lld",ans);
	}
	else
	{
		cnt=n/K;
		ans=cnt*cnt*cnt;
		printf("%lld",ans);
	}
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <string>
#include <set>
#include <iomanip>
#include <map>
#include <stdio.h>
#include <queue>
#define rep(i,n) for (int i=0;i<(n);++i)
#define REP(i,n) for (int i=0;i<=(n);++i)
#define all(x) (x).begin(), (x).end()

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

using namespace std;
typedef long long ll;
const int INF = 10000000;

int main() {
    ll a, b, n;
    cin >> a >> b >> n;
    ll x = min(b-1, n);
    cout << (a*x/b) - a * (x / b) << endl;
    return 0;
}

Measured memory_bytes: 3544
import Data.List

main = do
  n <- readLn
  putStrLn $ show n ++ ": " ++ unwords (fmap show $ primeFactor n)

factors :: Int -> [Int]
factors n = [d | d <- [1..n], n `mod` d == 0]

isPrime :: Int->Bool
isPrime x =
  null [y | y<-[2..floor $ sqrt $ fromIntegral x], x `mod` y == 0]

primeFactor :: Int -> [Int]
primeFactor n
  | isPrime n = [n]
  | otherwise = reverse $ go [] n
  where
    --go 1 = []
    --go n = d : go (n `div` d)
    go res 1 = res
    go res n = go (d : res) (n `div` d)
      where d = factors n !! 1

Measured memory_bytes: 4052
n = int(input())
c1 = 0
c2 = 0
c3 = 0
c4 = 0
for i in range(n):
    verd = input()
    if verd == "AC":
        c1 += 1
    elif verd == "WA":
        c2 += 1
    elif verd == "TLE":
        c3 += 1
    else:
        c4 += 1
print("AC x " + str(c1))
print("WA x " + str(c2))
print("TLE x " + str(c3))
print("RE x " + str(c4))


Measured memory_bytes: 9140