akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
template<typename T>
struct BIT{ //1-indexed
    vector<T> bit;
    int size;
    BIT(int n):size(n), bit(n+1, 0){}
    T sum(int i){
        T s=0;
        while(i>0){
            s+=bit[i];
            i-=(i&(-i));
        }
        return s;
    }
    void add(int i, T x){
        while(i<=size){
            bit[i]+=x;
            i+=(i&(-i));
        }
    }
};
int main()
{
	int n, q; scanf("%d %d", &n, &q);
	BIT<int> b(n);
	for(int z=0; z<q; z++){
		int c, x, y;
		scanf("%d %d %d", &c, &x, &y);
		if(c==0) b.add(x, y);
		else printf("%d\n", b.sum(y)-b.sum(x-1));
	}
	return 0;
}


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

int main() {
    int n, h, w, ans=0;
    cin >> n >> h >> w;
    REP(i,n){
        int a, b;
        cin >> a >> b;
        if(a>=h && b>=w)ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
char s[100];
int main()
{
	cin>>s;
	for(int i=0;i<=strlen(s);i++) {
		if(s[i]=='A'&&s[i+1]=='C')
		{
			cout<<"Yes"<<endl;
			return 0; 				
		}
	}
	cout<<"No"<<endl;
	return 0;
}

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

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

  int H, W; cin >> H >> W;
  vector<string> s(H);
  rep(i, H) cin >> s[i];

  int dh[] = {-1, 0, 1, 0};
  int dw[] = {0, -1, 0, 1};

  bool can = true;
  rep(i, H) rep(j, W) {
    if(s[i][j] == '#') {
      bool flag = false;
      rep(k, 4) {
        int h = i+dh[k];
        int w = j+dw[k];
        if(0<=h && 0<=w && h<H && w<W && s[h][w] == '#') flag = true;
      }
      if(!flag) can = false;
    }
  }
  cout << (can ? "Yes" : "No") << '\n';
  return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) throws IOException {
				
		BufferedReader input=new BufferedReader(new InputStreamReader(System.in));
		Scanner sc = new Scanner(input);
		
	    while(true){
	    	int a=sc.nextInt();
	    	int b=sc.nextInt();
	    	if(a==0&&b==0){sc.close();break;}
	    	else if(a<b)System.out.println(a+" "+b);
	    	else System.out.println(b+" "+a);
	    	}
	    }
	     	
	}

Measured memory_bytes: 26616
#include <cstdio>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <iterator>
#define loop(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define debug(x)  cout << #x << " = " << (x) << endl;

using namespace std;
using LL = long long;
using ULL = unsigned long long;

struct UnionFind {
    vector<int> par;

    UnionFind(int n) {
        par.assign(n, -1);
    }

    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    bool is_same(int x, int y) {
        return root(x) == root(y);
    }
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    int size(int x) {
        return -par[root(x)];
    }
};

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

    vector<int> a(m), b(m);
    rep(i, m) {
        cin >> a[i] >> b[i];
        --a[i]; --b[i];
    }

    int ans = 0;
    rep(i, m) {
        UnionFind uf(n);
        rep(j, m) if (j != i) uf.merge(a[j], b[j]);

        int cnt = 0;
        rep(j, n) if (j == uf.root(j)) ++cnt;

        if (1 < cnt) ++ans;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
	int a, b, c;
	int num = 0;
	cin >> a >> b >> c;
	for (int i = a; i <= b; i++)
	{
		if (c%i == 0)num += 1;
	}
	cout << num << endl;

	return 0;
}

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

int main() {
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	if (a + b > c + d)cout << "Left" << endl;
	else if (a + b == c + d)cout << "Balanced" << endl;
	else cout << "Right" << endl;
}

Measured memory_bytes: 256
def is_unique(seq):
    return len(seq) == len(set(seq))

word_num = int(input())

word_list=[]
for i in range(word_num):
  word_list.append(str(input()))
  if(is_unique(word_list) == False):
      print("No")
      exit()



# print(word_list)
temp = 0
for item in word_list:
  initial_word = item[0]
  last_word = item[-1]
  if(temp != initial_word and temp != 0):
      print("No")
      exit()
  temp = last_word
  # print("Ok")
print("Yes")


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

using namespace std;

int n;
map<int, set<pair<int, int>>> edge;
vector<long long> cost;

void dfs(int k) {
  cost[k] = 0;
  queue<int> q;
  q.push(k);
  while (!q.empty()) {
    auto u = q.front();
    q.pop();
    for (auto vs: edge[u]) {
      int v = vs.first, l = vs.second;
      if (cost[v] != 1e18) {
        continue;
      }
      cost[v] = cost[u] + l;
      q.push(v);
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  scanf("%d", &n);
  for (int i = 0; i < n - 1; i++) {
    int u, v, l;
    scanf("%d %d %d", &u, &v, &l);
    edge[u].insert(make_pair(v, l));
    edge[v].insert(make_pair(u, l));
  }
  int q, k;
  scanf("%d %d", &q, &k);
  cost = vector<long long>(n + 1, 1e18);
  dfs(k);
  for (int i = 0; i < q; i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    long long ans = cost[x] + cost[y];
    printf("%lld\n", ans);
  }
  return 0;
}

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

const char wall = '#';
vector<vector<char>> fields;
vector<vector<bool>> used;
vector<vector<ll>> dist;
const int dx[4] = {0, -1, 0, 1};
const int dy[4] = {1, 0, -1, 0};

const int D = 60; // 2^60 > 10^18的な
const int MAX_N = 200005;
int to[D][MAX_N];

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

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

  ll n, k;
  cin >> n >> k;
  rep(i, n) {
    cin >> to[0][i];
    to[0][i]--;
  }
  rep(i, D-1) {
    rep(j, n) {
      to[i+1][j] = to[i][to[i][j]];
    }
  }
  
  int v = 0;
  for (int i = D-1; i >= 0; --i) {
    ll l = 1ll << i; // 1 << i だとオーバーフローする
    if (l <= k) {
      v = to[i][v];
      k -= l;
    }
  }
  cout << v+1 << endl;
  return 0;
}


Measured memory_bytes: 50552
n, m = (int(xi) for xi in input().split())
k = []
for xi in range(m):
    ksub = [int(xi) for xi in input().split()]
    k.append(ksub[1:])
p = [int(xi) for xi in input().split()]

# print(k)


countN = 0
for Nnum in range(2**n):
    txt = bin(Nnum)[2:]
    txt = "0"*(n-len(txt))+txt
    # print(txt)

    for li in range(m):
        ltxt = "0"*n
        for xi in range(len(k[li])):
            point = k[li][xi]-1
            ltxt = ltxt[:point]+"1"+ltxt[point+1:]
        # print(ltxt)
        count = 0
        for xi in range(n):
            if txt[xi]=="1" and ltxt[xi]=="1":
                count += 1
        if count%2==p[li]:
            switch = True
        else:
            switch = False
            break
    if switch: countN += 1

print(countN)


Measured memory_bytes: 9008
def main():
    n = int(input())
    cor = [tuple(map(int, input().split())) for i in range(n)]

    cor.sort(reverse=True, key=lambda tup: tup[2])

    for i in range(101):
        for j in range(101):
            if cor[0][2]:
                h = cor[0][2] + abs(i-cor[0][0]) + abs(j-cor[0][1])
            else:
                h = 1

            for x, y, hi in cor:
                if max(h-abs(i-x)-abs(j-y), 0) != hi:
                    break

            else:
                print(i, j, h)
                exit()


if __name__ == '__main__':
    main()


Measured memory_bytes: 41200
#include<bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; i++)
#define repo(i, n) for(int i=1; i<=n; i++)
#define INF 1001001001
#define INFll 100100100100100
// debug用
#define PrintVec(x) for (auto elementPrintVec: x) { cout << elementPrintVec << " "; } cout << endl;

using namespace std;
using ull = unsigned long long;
using ll = long long;
using P = pair<int, int>;
const int mod = 1000000007;

ll dp[105][4][2];

int main(){
  string n;
  cin >> n;
  int sz=n.size();
  int k;
  cin >> k;

  rep(i, sz)rep(j, k+1)rep(l, 2){
    dp[i][j][l]=0;
  }
  dp[0][0][0]=1;
  /*
  rep(i, sz)rep(j, k+1)rep(l, 2){
    int nsz=n[sz-i-1]-'0';
    rep(dig, 10){
      if(dp[i][j][l]>1e9)continue;
      if(dig==0 && nsz>0){
        if(dp[i+1][j][0]>1e9)continue;
        dp[i+1][j][0]+=dp[i][j][l];
      } else if(dig==0 && nsz==0){
        if(dp[i+1][j][l]>1e9)continue;
        dp[i+1][j][l]+=dp[i][j][l];
      } else if(nsz>dig && dig!=0 && j+1<=k){
        if(dp[i+1][j+1][0]>1e9)continue;
        dp[i+1][j+1][0]+=dp[i][j][l];
      } else if(nsz==dig && dig!=0 && j+1<=k){
        if(dp[i+1][j+1][l]>1e9)continue;
        dp[i+1][j+1][l]+=dp[i][j][l];
      } else if(nsz<dig && dig!=0 && j+1<=k){
        if(dp[i+1][j+1][1]>1e9)continue;
        dp[i+1][j+1][1]+=dp[i][j][l];
      }
    }

  }*/

  rep(i, sz)rep(j, k+1)rep(l, 2){
    int nsz=n[i]-'0';
    rep(dig, 10){
      if(dig==0 && nsz>0){
        dp[i+1][j][1]+=dp[i][j][l];
      } else if(dig==0 && nsz==0){
        dp[i+1][j][l]+=dp[i][j][l];
      } else if(nsz>dig && dig!=0 && j+1<=k){
        dp[i+1][j+1][1]+=dp[i][j][l];
      } else if(nsz==dig && dig!=0 && j+1<=k){
        dp[i+1][j+1][l]+=dp[i][j][l];
      } else if(nsz<dig && j+1<=k && l==1){
        dp[i+1][j+1][l]+=dp[i][j][l];
      }
    }
  }

  cout << dp[sz][k][1]+dp[sz][k][0] << endl;
  return 0;
}


Measured memory_bytes: 3588
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <utility>
#include <set>
#include <queue>
using namespace std;
typedef long long int ll;
typedef long double ld;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
typedef pair<ll,ll> pairs;
vector<pairs> p;
bool pairCompare(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.first < secondElof.first;
}
bool pairCompareSecond(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.second < secondElof.second;
}
#define MAX_N 100100
#define MOD 1000000007
bool x[MAX_N];
ll num[MAX_N];
ll fibl[MAX_N]={0};
// 四方向への移動ベクトル
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

ll fib(ll a){
    if (fibl[a]!=0)return fibl[a];
    if (a==0){
        return 0;
    }else if (a==1){
        return 1;
    }
    return fibl[a]=fib(a-1)+fib(a-2);
}
 
ll eratosthenes(ll n) {
    int p = 0;
    for (ll i=0; i<=n; ++i) x[i] = true;
    x[0] = x[1] = false;
    for(int i=2; i<=n; ++i) {
        if(x[i]) {
            p++;
            for(int j=2*i; j<=n; j+=i) x[j] = false;
        }
        
        num[i] = p;
    }
    return p;
}
 
ll gcd(ll a,ll b){
    if (a%b==0)return(b);
    else return(gcd(b,a%b));
}
 
ll keta(ll N){
    int tmp{};
    while( N > 0 ){
        tmp += ( N % 10 );
        N /= 10;
    }
    N = tmp;
    return N;
}
#define PI 3.14159265359
int main(){
    ld n;
    cin >> n;
    cout << (n*2)*PI << endl;
    return 0;
}



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

int main(){
    int a,b,n;
    int total;
    int c;
    while(cin >> a >> b >> n){
        total = 0;
        c = a%b*10;
        for(int i=0;i<n;i++){
            total += c/b;
            c = c%b*10;
        }
        cout << total << endl;
    }
}

Measured memory_bytes: 1156
/*
 * @Author: clorf 
 * @Date: 2020-08-31 20:27:12 
 * @Last Modified by: clorf
 * @Last Modified time: 2020-08-31 21:25:47
 */
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<ctime>
#define INF 1e9
using namespace std;
const int maxn=200010;
const double Pi=acos(-1.0);
template<class T>void read(T &x)
{
    x=0;int f=0;char ch=getchar();
    while(ch<'0'||ch>'9') {f|=(ch=='-');ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x=f?-x:x;
    return;
}
int n,q,cnt;
int fa[maxn];
long long p[maxn],ans;
struct edge
{
    int x;
    int y;
    long long z;
}s[maxn],e[maxn<<1];
inline bool cmp(edge a,edge b)
{
    return a.z<b.z;
}
inline int sub(int x)
{
    return (x+1)%n;
}
int getfa(int x)
{
    if(fa[x]==x)
        return x;
    return fa[x]=getfa(fa[x]);
}
int main()
{
    memset(p,0x3f,sizeof(p));
    scanf("%d%d",&n,&q);
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d%lld",&s[i].x,&s[i].y,&s[i].z);
        e[++cnt]=(edge){s[i].x,s[i].y,s[i].z};
        p[s[i].x]=min(p[s[i].x],s[i].z+1);
        p[s[i].y]=min(p[s[i].y],s[i].z+2);
    }
    int now=s[1].x,tot=3*n;
    long long sum=p[now];
    while(tot--)
    {
        if(sum<p[now])
            p[now]=sum;
        else
            sum=p[now];
        sum+=2;
        now=sub(now);
    }
    for(int i=0;i<n;i++)
        e[++cnt]=(edge){i,sub(i),p[i]};
    for(int i=0;i<=n;i++)
        fa[i]=i;
    sort(e+1,e+cnt+1,cmp);
    for(int i=1;i<=cnt;i++)
    {
        int x=getfa(e[i].x);
        int y=getfa(e[i].y);
        if(x!=y)
        {
            fa[x]=y;
            ans+=e[i].z;
        }
    }
    printf("%lld",ans);
    return 0;
}


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

ll gcd(ll a, ll b) {
    while ( b != 0 ) {
        ll t = b;
        b = a % b;
        a = t;
    }
    return a;
}

bool solve() {
    ll N, K, g, m, a;
    cin >> N >> K;
    m = 0;
    cin >> g;
    m = max(m, g);
    for ( int i = 1; i < N; i++ ) {
        cin >> a;
        m = max(m, a);
        g = gcd(g, a);
    }
    if ( K % g == 0 && K <= m ) return true;
    else return false;
}

int main() {
    string ans = solve() ? "POSSIBLE" : "IMPOSSIBLE";
    cout << ans << "\n";
    return 0;
}

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


using namespace std;

using ll   = long long;
using ii   = pair   < int , int >;
using i3   = pair   < int , ii  >;
using li   = pair   < ll  , int >;
using lii  = pair   < ll  , ii  >;
using pll  = pair   < ll  , ll  >;
using vi   = vector < int       >;
using vl   = vector < ll        >;
using vii  = vector < ii        >;
using vli  = vector < li        >;
using vpll = vector < pll       >;
using vi3  = vector < i3        >;
using vlii = vector < lii       >;


const int N = 2e5 + 5;
const ll INF = 1e17 + 7;
const double eps = 1e-9 , PI = acos(-1);



int n , m;


void solve(int testCase){

    scanf("%d %d" , &n , &m);
    printf("%s\n" , m >= n ? "unsafe" : "safe");

}

main(){

    int t = 1;
    // scanf("%d" , &t);

    for(int testCase = 1 ; testCase <= t ; testCase ++){
            solve(testCase);
    }

    return 0;
}


Measured memory_bytes: 3688
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define rep(i, n) for(int i=0;i<(int)(n);++i)
typedef pair<int, int> P;

inline P func(int a) {
  int cnt = a % 10;
  while (a >= 10) {
    a/=10;
  }
  return {cnt, a};
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n; cin >> n;
  map<P, int> mp;
  for (int i = 1; i <= n; ++i) {
    P p = func(i);
    mp[p]++;
  }
  lint ans = 0;
  for (int i = 1; i <= n; ++i) {
    P p = func(i);
    P q = {p.second, p.first};
    ans += mp[q];
  }
  cout << ans << '\n';
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

static const int N = 100;

int main(void) {
  int M[N][N];
  int n, u, k, v;

  cin >> n;

  //?????????
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
      M[i][j] = 0;
    }
  }

  //Graph -> Matrix
  for(int i = 0; i < n; i++) {
    cin >> u >> k;
    u--;//0-origian
    for(int j = 0; j < k; j++) {
      cin >> v;
      v--;
      M[u][v] = 1;
    } 
  }

  for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
      if(j) {
        cout << " ";
      }
      cout << M[i][j];
    }
    cout << endl;
  }
  return 0;
}

Measured memory_bytes: 1200
s = int(input())
A = [] 
m = 0
for i in range(1,1000001):
    if i == 1:
       A.append(s)
    else:
        if A[i - 2] % 2 == 0:
            if A[i - 2] / 2 in A:
                m = i
                break
            A.append(A[i - 2] / 2)
        else:
            if 3 * A[i - 2] + 1 in A:
                m = i
                break
            A.append(3 * A[i - 2] + 1)

print(m)

Measured memory_bytes: 9188
#!/usr/bin/env python3
import sys


def solve(A: int, B: int):
    temp1 = A + B
    temp2 = A - B
    temp3 = A * B
    ans_list = [temp1, temp2, temp3]
    print(max(ans_list))
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    solve(A, B)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
#include <iostream>
using namespace std;
#define cpy(a,b) tront[a-1] = temp[b-1]

class dice {
public:
	int tront[6];
	dice() {
		for (int i = 0; i < 6; i++) {
			cin >> tront[i];
		}
	}

	void rotation(char c) {
		int temp[6], i;
		for (i = 0; i < 6; i++)
			temp[i] = tront[i];
		switch (c) {
		case 'E':
			cpy(1, 4);
			cpy(4, 6);
			cpy(6, 3);
			cpy(3, 1);
			break;
		case 'N':
			cpy(5, 1);
			cpy(1, 2);
			cpy(2, 6);
			cpy(6, 5);
			break;
		case 'S':
			cpy(2, 1);
			cpy(1, 5);
			cpy(5, 6);
			cpy(6, 2);
			break;
		case 'W':
			cpy(1, 3);
			cpy(3, 6);
			cpy(6, 4);
			cpy(4, 1);
			break;
		}
	}

	void print(int x) {
		cout << tront[x-1] << endl;
	}
};

int main() {
	dice d;
	int i, j, q, a, b, m, n;
	int ans[7][7] = {0};
	ans[5][4]=1;ans[4][2]=1;ans[2][3]=1;ans[3][5]=1;
	ans[1][4]=2;ans[4][6]=2;ans[6][3]=2;ans[3][1]=2;
	ans[1][2]=3;ans[2][6]=3;ans[6][5]=3;ans[5][1]=3;
	ans[1][5]=4;ans[5][6]=4;ans[6][2]=4;ans[2][1]=4;
	ans[1][3]=5;ans[3][6]=5;ans[6][4]=5;ans[4][1]=5;
	ans[3][2]=6;ans[2][4]=6;ans[4][5]=6;ans[5][3]=6;
	cin >> q;
	for (i = 0; i < q; i++) {
		cin >> a >> b;
		for (j = 0; j < 6; j++) {
			if (a == d.tront[j])
				m = j+1;
			if (b == d.tront[j])
				n = j+1;
		}
		d.print(ans[m][n]);
	}	
	return 0;
}

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

#define int long long





int findRecAns(vector<int> &w,vector<int> &p,int maxW,vector<vector<int>>&dp,int pos)
{
    int n=w.size();

    if(maxW<=0)
    {
        // dp[pos][maxW]=0;
        return 0;
    }
    if(n-1==pos)
    {
        if(w[pos]<=maxW)
        {
            dp[pos][maxW]=p[pos];
            return p[pos];
        }
        else
        {

            return 0;
        }
    }

    if(dp[pos][maxW]!=-1)
    {
        return dp[pos][maxW];
    }
    int take=0;
    int leave=0;

    if(w[pos]<=maxW)
    {
        take=p[pos]+findRecAns(w,p,maxW-w[pos],dp,pos+1);
    }
    leave=findRecAns(w,p,maxW,dp,pos+1);



    dp[pos][maxW]=max(take,leave);

    return dp[pos][maxW];







}

int32_t main()
{
    int n,W;
    cin>>n>>W;

    vector<int> w(n);
    vector<int> p(n);

    for(int x=0;x<n;x++)
    {
        cin>>w[x]>>p[x];
    }

    vector<vector<int>> dp(n,vector<int>(W+3,-1));
    int wt;
    int ans=findRecAns(w,p,W,dp,0);
    cout<<ans<<endl;
}

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

ll a, b, ans=0,h, w, fac[202020];

ll mp(ll a, ll p){

if(p==0)return 1%mod;
ll u = mp(a, p/2);
u = (u*u)%mod;
if(p%2==1)u = (u*a)%mod;
return u;

}


ll c(ll n, ll k){

ll x = fac[n]*mp(fac[n-k], mod-2)%mod * mp(fac[k], mod-2)%mod;
return x;

}


int main(){
fac[0]=1;
rep(i, 1, 202020){
fac[i]= (fac[i-1]*i)%mod;
}

cin >> h >> w >> a >> b;

rep(i, b+1, w){

ans += (c(i-1+h-a-1, i-1)*c(a-1+w-i,a-1))%mod ;
//cout << ans << endl;
}

cout << ans%mod << endl;

return 0;}


Measured memory_bytes: 1792
n,m,X,Y=map(int,input().split())
x=list(map(int,input().split()))
y=list(map(int,input().split()))
a=max(x)
b=min(y)
if a>=b:
  print('War')
else:
  for i in range(a+1,b+1):
    if X<i<=Y:
      print('No War')
      break
    print('War')

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define ll   long long int
void fast()
{
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   cout.tie(NULL);
}

int main(void)
{
  fast();
  ll n,k;
  cin>>n>>k;
  ll rem=0;
  vector<ll> v;
  while(n>0)
  {
      rem=n%k;
      v.push_back(rem);
      n=n/k;
  }
  cout<<v.size()<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch-'0'<0||ch-'0'>9){if(ch=='-') f=-1;ch=getchar();}
    while(ch-'0'>=0&&ch-'0'<=9){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll re[15][15];
int dis[]={0,1,2,4,7,12,20,29,38,52,73};
int n;
int book[15];
int a[15];
int vis[15];
ll mx;
void dfs(int x,int n)
{
    if(x>n)
    {
        ll tmp=0;
        for(int i=2;i<=n;i++)  tmp=tmp+re[a[i-1]][a[i]];
        mx=max(mx,tmp);
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            a[i]=x;
            vis[i]=1;
            dfs(x+1,n);
            vis[i]=0;
        }
    }
}
int main()
{
    n=read();
    re[1][2]=re[2][1]=1;
    for(int i=3;i<=n;i++)
    {
        mx=0;
        dfs(1,i-1);
        for(int j=1;j<i;j++)  re[i][j]=re[j][i]=(ll)dis[j]*(mx+1);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)  printf("%lld ",re[i][j]);
        puts("");
    }
    return 0;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
	"sort"
	"strconv"
)

func main() {
	var a, b, c int
	fmt.Scan(&a)
	fmt.Scan(&b)
	fmt.Scan(&c)
	numbers := []int{a, b, c}
	sort.Ints(numbers)
	fmt.Println(strconv.Itoa(numbers[0]) + " " + strconv.Itoa(numbers[1]) + " " + strconv.Itoa(numbers[2]))
}

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

int main()
{
  int K, S;
  cin >> K >> S;
  
  int count = 0;
  rep(i, K+1)
  {
    rep(j, K+1)
    {
      if (S-i-j <= K && S-i-j >= 0)
        count++;
    }
  }
  cout << count << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
    #include <math.h>
 
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    # define M_PI  3.14159265358979323846
 
 
    const int M=1e9+7;
    long long mod(long long x){
        return ((x%M + M)%M);
    }
    long long add(long long a, long long b){
        return mod(mod(a)+mod(b));
    }
    long long mul(long long a, long long b){
        return mod(mod(a)*mod(b));
    }

    void solve(){  
        ll d,t,s;
        cin>>d>>t>>s;
        ll a=t*s;
        if(a>=d)
            cout<<"Yes";
        else{
            cout<<"No";
        }
    }
    int main(){
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        cout<<fixed;
        cout<<setprecision(10);
//        freopen("timber_input.txt", "r", stdin);
//        freopen("timber_output.txt", "w", stdout);
        int t=1;
        // cin>>t;
        for(int i=1;i<=t;i++){
//            cout<<"Case #"<<i<<": ";
            solve();
        }
        return 0;
    }


Measured memory_bytes: 3648
# -*- coding utf-8 -*-
from collections import defaultdict

MOD = 10 ** 9 + 7
N, Q = map(int, input().split())

tree = defaultdict(set)
for i in range(N - 1):
    a, b = map(int, input().split())
    tree[a].add(b)
    tree[b].add(a)

counter = defaultdict(int)
for i in range(Q):
    p, x = map(int, input().split())
    counter[p] += x

cur_node = set()
cur_node.add(1)
pre_node = set()
while len(cur_node) != 0:
    next_node = set()
    for ni in cur_node:
        for nj in tree[ni]:
            if {nj} <= pre_node:
                continue
            counter[nj] += counter[ni]
            next_node.add(nj)
    pre_node = cur_node
    cur_node = next_node

print(' '.join((str(counter[i]) for i in range(1, N + 1))))


Measured memory_bytes: 125740
#include<bits/stdc++.h>
using namespace std;int N,C,D[2][5001],i,j,*A,*B;
main(){A=*D,B=D[1];cin>>N;fill_n(*D,1e4+2,1e9);A[1]=B[0]=0;for(;i++<N-1&&cin>>C;)for(j=N/2;~j;)A[j+1]=min(A[j],B[j]+C),B[j--]=min(A[j]+C,B[j]);cout<<min(A[N/2],B[N/2])<<endl;}

Measured memory_bytes: 1204
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (int)(n) - 1; i >= 0; i--)
#define range(a) a.begin(), a.end()
using namespace std;
using ll = long long;

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<int> a(n);
  vector<int> plus, minus;
  rep(i, n) cin >> a[i];
  sort(a.begin(), a.end());
  vector<bool> used(n);
  vector<int> xs, ys;
  rep(i, n - 1) {
    if (i > 0 && a[i] > 0) {
      xs.push_back(a[0]);
      ys.push_back(a[i]);
      a[0] -= a[i];
      used[i] = true;
    }
  }
  rep(i, n - 1) {
    if (!used[i]) {
      xs.push_back(a[n - 1]);
      ys.push_back(a[i]);
      a[n - 1] -= a[i];
    }
  }
  cout << a[n - 1] << '\n';
  rep(i, xs.size()) {
    cout << xs[i] << ' ' << ys[i] << '\n';
  }
}


Measured memory_bytes: 3316
//use itertools::Itertools;
use std::cmp;
use std::collections::BinaryHeap;
use std::collections::HashMap;
use std::collections::HashSet;
use std::collections::VecDeque;
use std::io::Read;
use std::usize::MAX;

macro_rules! input {(source = $s:expr, $($r:tt)*) => {let mut iter = $s.split_whitespace();let mut next = || { iter.next().unwrap() };input_inner!{next, $($r)*}};($($r:tt)*) => {let stdin = std::io::stdin();let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));let mut next = move || -> String{bytes.by_ref().map(|r|r.unwrap() as char).skip_while(|c|c.is_whitespace()).take_while(|c|!c.is_whitespace()).collect()};input_inner!{next, $($r)*}};}
macro_rules! input_inner {($next:expr) => {};($next:expr, ) => {};($next:expr, $var:ident : $t:tt $($r:tt)*) => {let $var = read_value!($next, $t);input_inner!{$next $($r)*}};}
macro_rules! read_value {($next:expr, ( $($t:tt),* )) => {( $(read_value!($next, $t)),* )};($next:expr, [ $t:tt ; $len:expr ]) => {(0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()};($next:expr, chars) => {read_value!($next, String).chars().collect::<Vec<char>>()};($next:expr, usize1) => {read_value!($next, usize) - 1};($next:expr, [ $t:tt ]) => {{let len = read_value!($next, usize);(0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()}};($next:expr, $t:ty) => {$next().parse::<$t>().expect("Parse error")};}

fn solve() {
    input! {
        t: chars
    }

    for i in 0..t.len() {
        if t[i] == '?' {
            print!("D");
        } else {
            print!("{}", t[i]);
        }
    }
    println!();
}

fn main() {
    let thd = std::thread::Builder::new().stack_size(104_857_600);
    thd.spawn(|| solve()).unwrap().join().unwrap();

    /*
    // 入力を一括で読み込む場合
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();
    let mut input = buf.split_whitespace();

    // inputに対しnext()で読み込んでいく
    let q: usize = input.next().unwrap().parse().unwrap();
    */
}

const LARGE_PRIME: u64 = 1_000_000_007;

// @〜でsnippet


Measured memory_bytes: 2272
from heapq import heappush, heappop
rot1 = [1,2,3,4,5,6,22,23,24,12,11,10,18,14,15,16,17,13,19,20,21,7,8,9,25,26,27,28,29,30]
rot2 = [28,29,30,4,5,6,7,8,9,10,11,12,13,14,16,15,17,18,21,20,19,22,23,24,25,26,27,1,2,3]
rot3 = [24,2,3,27,5,6,30,8,9,21,11,12,13,14,15,18,17,16,19,20,10,22,23,1,25,26,4,28,29,7]
rot4 = [1,2,22,4,5,25,7,8,28,10,11,19,15,14,13,16,17,18,12,20,21,3,23,24,6,26,27,9,29,30]
N = int(input())
for _ in range(N):
    closeset = set()
    finstate = (1,1,1,1,1,1,1,1,1,2,2,2,4,4,4,6,6,6,5,5,5,3,3,3,3,3,3,3,3,3)
    state = tuple(map(int,input().split()))
    que = [(0,state,0)]
    while que:
        numope, cstate, lasope = heappop(que)
        if cstate == finstate: break
        if cstate in closeset: continue
        closeset.add(cstate)
        for ope,rot in zip(range(1,5),[rot1,rot2,rot3,rot4]):
            if lasope != ope:
                nstate = tuple(cstate[i-1] for i in rot)
                heappush(que,(numope+1,nstate,ope))
    print(numope)


Measured memory_bytes: 5676
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <functional>
#include <string>
#include <cstdlib>
#include <numeric>
#include <cstdbool>
#include <cstring>
#include <map> 
#include<set>
#include<queue>
#include <iomanip>

typedef long long ll;

#define rep(i,n) for(ll i=0;i<n;i++)
using namespace std;

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

const long long INF = 1000000000000000;
const ll inf = -1e18;
typedef pair<ll, ll> P;
ll ma = 1000000000 + 7;
ll mx = 1000003;
ll h,n, w,m,t; string s;
ll R, C;
ll sy, sx, gy, gx;
char maze[20][20];
ll dis[20][20];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
ll gcd(ll x, ll y) {
	if (x % y == 0) return y;
	return gcd(y, x % y);
}
ll lcm(ll a,ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
void comb(vector<vector <ll> >& v) {
	for (ll i = 0; i < v.size(); i++) {
		v[i][0] = 1;
		v[i][i] = 1;
	}
	for (ll k = 1; k < v.size(); k++) {
		for (int j = 1; j < k; j++) {
			v[k][j] = (v[k - 1][j - 1] + v[k - 1][j])%ma;
		}
	}
}

ll GetDigit(ll num) {
	return log10(num) + 1;
}
ll Combination(int n, int r)
{
	if (n - r < r) r = n - r;
	if (r == 0) return 1;
	if (r == 1) return n;

	vector<ll> numerator(r);
	vector<ll> denominator(r);

	for (int k = 0; k < r; k++)
	{
		numerator[k] = n - r + k + 1;
		denominator[k] = k + 1;
	}

	for (int p = 2; p <= r; p++)
	{
		int pivot = denominator[p - 1];
		if (pivot > 1)
		{
			int offset = (n - r) % p;
			for (int k = p - 1; k < r; k += p)
			{
				numerator[k - offset] /= pivot;
				denominator[k] /= pivot;
			}
		}
	}

	ll result = 1;
	for (int k = 0; k < r; k++)
	{
		if (numerator[k] > 1) result *= numerator[k];
		result %= ma;
	}

	return result;
}

ll bfs() {
	queue<P> que;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) dis[i][j] = INF;
	}
	que.push(P(sy - 1, sx - 1));
	dis[sy - 1][sx - 1] = 0;

	while (que.size() > 0) {
		P p = que.front();
		que.pop();
		if (p.first == gy - 1 && p.second == gx - 1) break;
		for (ll i = 0; i < 4; i++) {
			ll ny = p.first + dy[i];
			ll nx = p.second + dx[i];
			if (0 <= ny && ny < R && 0 <= nx && nx < C && maze[ny][nx] == '.' && dis[ny][nx] == INF) {
				que.push(P(ny, nx));
				dis[ny][nx] = dis[p.first][p.second] + 1;
			}
		}
	}
	return dis[gy - 1][gx - 1];
}
ll dp[20500];
int main() {
	cin >> n;
	ll k;
	cin >> k;
	vector<ll> x(n);
	rep(i, n) {
		cin >> x[i];
	}
	ll res = 0;
	rep(i, n) {
		res += 2*min(x[i], abs(k - x[i]));
	}
	cout << res << endl;
}



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

int main()
 {
 	int n,i,d,c=0;
 	cin>>n;
 	int a[n],b[n];
 	for(i=0;i<n;i++)
 		cin>>a[i];
 	for(i=0;i<n;i++)
 		b[i]=a[i];
 	sort(a,a+n);
 	for(i=0;i<n;i++)
 		{
 			if(a[i]!=b[i])
 				c++;
		 }
	if(c<=2)
		cout<<"YES"<<endl;
	else
		cout<<"NO"<<endl;
 	
}

Measured memory_bytes: 3640
H, W = map(int, input().split())
s = [input() for i in range(H)]

for i in range(H):
  for j in range(W):
    if s[i][j] == '#':
      count = 0
      for k in [[1,0], [0, 1], [-1, 0], [0, -1]]:
        if 0 <= i+k[1] < H and 0 <= j+k[0] < W:
          if s[i+k[1]][j+k[0]] == '#':
            count += 1
          else:
            pass
      if count == 0:
        print('No')
        exit()
      else:
        pass
    else:
      pass

print('Yes')

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

int main()
{
	string str;
	int w;

	cin >> str;
	cin >> w;

	const char *ptr = str.c_str();

	for (int i = 0; i < str.length(); i += w)
	{
		cout << ptr[i];
	}

	cout << endl;
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i,n) for(int i=0; i < (n); ++i)
#define REPR(i,n) for(int i=(n); i >=0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
 
typedef long long ll;
#define INF 1e9
 
int main(){
  int N;
  cin >> N;
  vector<int> a(N);
  REP(i, N){
    cin >> a[i];
  }

  sort(a.begin(), a.end());

  int cnt = 0;
  int cur = a[0];
  int ans = 0;
  REP(i, N){
    if(cur != a[i]){
      if(cur < cnt){
        ans += cnt - cur;
      }
      else if(cur > cnt){
        ans += cnt;
      }
      cnt = 1;
      cur = a[i];
    }
    else{
      cnt++;
    }
  }
  if(cur < cnt){
    ans += cnt - cur;
  }
  else if(cur > cnt){
    ans += cnt;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int n,m,s=1,num;
struct A{
	int p,t;
}a[100010];
bool cmp(const A& a,const A& b) {
	return a.t<b.t;
}
priority_queue<int> ans;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%d%d",&a[i].t,&a[i].p);
	sort(a+1,a+n+1,cmp);
	for(int i=m;i>=1;--i) {
		while(a[s].t+i-1<=m&&s<=n) ans.push(a[s].p),s++;
		if(!ans.empty()) num+=ans.top(),ans.pop();
	}
	printf("%d",num);
	return 0;
}

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

#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF 1e9
typedef long long ll;


int main() {
    ll A,B,K; cin >> A >> B >> K;
    if(A>=K){
        cout << A-K << " " << B << endl;
    }else if(A<K && K-A <= B){
        cout << 0 << " " << B+A-K << endl;
    }else{
        cout << 0 << " " << 0 << endl;
    }
    return 0;
}

Measured memory_bytes: 3572
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 8;
int n, answer=0, v[1+MAXN];
bool edge[1+MAXN][1+MAXN], seen[1+MAXN];

void Backtracking(int x){
    if(x == n + 1) {
        answer++;
        return;
    }
    for (int i = 1; i <= n; i++){
        if (!seen[i] && edge[v[x - 1]][i]) {
            v[x] = i;
            seen[i] = true;
            Backtracking(x + 1);
            seen[i] = false;
        }
    }
}

int main() {
  int m;
  answer = 0;
  cin >> n >> m;
  int temp_1, temp_2;
  for(int i = 0; i < m; ++i){
    cin >> temp_1 >> temp_2;
    edge[temp_1][temp_2] = edge[temp_2][temp_1] = true;
  }
  v[1] = 1;
  seen[1] = true; // check point
  Backtracking(2);
  cout << answer << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repp(i, a, b) for (int i = a; i <= (b); ++i)
#define repr(i, a, b) for (int i = a; i >= (b); --i)
#define bit(n) (1LL << (n))
#define len(x) ((ll)(x).size())
#define debug(var) cout << "[" << #var << "]\n" << var << endl
#define int long long
typedef long long ll;
const int INF = 1001001001001001001ll;
const ll LINF = 1001001001001001001ll;
const int MOD = 1000000007;
const double EPS = 1e-9;

template <typename T>
ostream& operator<<(ostream& s, const vector<T>& v) {
  int len = v.size();
  for (int i = 0; i < len; ++i) {
    s << v[i];
    if (i < len - 1)
      s << ' ';
  }
  return s;
}

template <typename T>
ostream& operator<<(ostream& s, const vector<vector<T>>& vv) {
  int len = vv.size();
  for (int i = 0; i < len; ++i) {
    s << vv[i];
    if (i != len - 1)
      s << '\n';
  }
  return s;
}

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

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

__attribute__((constructor)) void initial() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
}

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

  int N = len(S);
  int res = N - 8;
  cout << S.substr(0, res) << endl;
}

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

signed main() {
    int n, k; cin >> n >> k;
    int left = 0, right = 1e18+1;
    while (left + 1 < right) {
        int mid = (left + right) / 2;
        
        int tmp = mid;
        rep(i, n) {
            tmp -= (tmp - 1) / k + 1;
        }
        if (tmp >= 0) right = mid;
        else left = mid;
    }
    cout << right - 1 << endl;
}

Measured memory_bytes: 3076
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int N;
  cin >> N;
  string S;
  cin >> S;
  for(int i=0;i<S.size();i++){
    int p=S.at(i)-'A';
    int ans='A'+((p+N)%26);
    cout << char(ans);
  }
  cout << endl;
}

Measured memory_bytes: 256
using System;

class Program
{
    static void Main()
    {
        string[] s = Console.ReadLine().Split(' ');
        // 0:W, 1:H, 2:x, 3:y, 4:r
        int[] i = new int[s.Length];

        for (int j = 0; j < s.Length; j++)
            i[j] = int.Parse(s[j]);

        String ret = "";
        if (   ((i[2]-i[4]) >= 0 && (i[3]+i[4]) <= i[1])
            && ((i[3]-i[4]) >= 0 && (i[2]+i[4]) <= i[0]))
            ret = "Yes";
        else
            ret = "No";
        
        Console.WriteLine(ret);
    }
}


Measured memory_bytes: 8976
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n,inv10;
char s[N];
map<pair<int,int>,int>vis;
ll qpow(ll a,ll n,ll mod)
{
    ll ans=1;
    while(n)
    {
        if(n&1) ans=ans*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return ans;
}
int mod1=3,mod2=673;
int main()
{
    int inv10_1=qpow(10,mod1-2,mod1);
    int inv10_2=qpow(10,mod2-2,mod2);
    scanf("%s",s+1);
    vis[{0,0}]++;
    int sum1=0,sum2=0;
    ll ans=0,k1=1,k2=1;
    for(int i=1;s[i];i++)
    {
        k1=k1*inv10_2%mod1;
        k2=k2*inv10_2%mod2;
        sum1=(sum1+(ll)(s[i]-'0')*k1%mod1)%mod1;
        sum2=(sum2+(ll)(s[i]-'0')*k2%mod2)%mod2;
        ans+=vis[{sum1,sum2}];
        vis[{sum1,sum2}]++;
    }
    printf("%lld\n",ans);
}



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

const int inf = 1e9;
const ll linf = 1e18;

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

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

using namespace std;
int main(){
  int w,h,x,y,r;
  cin >> w >> h >> x >> y >> r;
  if(w < x+r || 0>x-r) cout << "No" << endl;
  else if(h < y+r || 0>y-r) cout << "No" << endl;
  else cout << "Yes" << endl;
  return 0;
}


Measured memory_bytes: 3096
#include<bits/stdc++.h>
using namespace std;
int main(){
  int l,r;
  cin>>l>>r;
  int ans=2020;
  if(r-l>=2019){cout<<0; return 0;}
  for(int i=l;i<r;i++){
    for(int j=i+1;j<=r;j++){
      int a=i%2019;
      int b=j%2019;
      ans=min(ans,a*b%2019);
    }
  }
  cout<<ans;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define MOD (int) (1e9+7)
#define INF (int) 2e9
#define LLINF (ll) 2e18

int main(){
    int n, k, c;
    string s;
    cin >> n >> k >> c >> s;

    int i = 0;
    vector<int> l, r;
    while(i<n){
        if(s[i]=='o'){
            l.emplace_back(i);
            if(l.size()==k) break;
            i += c+1;
        }else{
            i++;
        }
    }

    i = n-1;
    while(i>=0){
        if(s[i]=='o'){
            r.emplace_back(i);
            if(r.size()==k) break;
            i -= c+1;
        }else{
            i--;
        }
    }

    sort(r.begin(), r.end());

    rep(i, k){
        if(l[i]==r[i]) cout << l[i]+1 << endl;
    }
    // printf("%d\n", N);
    return 0;
}

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

#define fir first
#define sec second
#define MP make_pair
#define PB push_back

using namespace std;
typedef long long LL;
typedef unsigned long long u64;

template <typename T> inline bool cmin(T & a, const T & b) { return a > b ? a = b, 1 : 0;}
template <typename T> inline bool cmax(T & a, const T & b) { return a < b ? a = b, 1 : 0;}
int read() {
	int x = 0, f = 1;char ch;
	for(ch = getchar(); !isdigit(ch); ch = getchar())
		if(ch == '-') f = -1;
	for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
	return x * f;
}

const int MaxN = 2333;
int n, a[MaxN];

bitset<MaxN * MaxN> f[2];
int main() {
	int i;
	n = read();
	for(i = 1; i <= n; i++) a[i] = read();
	if(n == 1) return printf("%d\n", a[n]), 0;
	f[0].set(0);
	
	for(i = 1; i <= n; i++) {
		f[i & 1] = f[~i & 1];
		f[i & 1] |= f[~i & 1] << a[i];
	}
	int s = 0;
	for(i = 1; i <= n; i++) s += a[i];
	
	for(i = s + 1 >> 1; ; i++)
		if(f[n & 1][i])
			return printf("%d\n", i), 0;
	return 0;
}




Measured memory_bytes: 3072
#include <bits/stdc++.h>
#define rep(i,m,n) for(int i=m; i<n; i++)
#define co(n) cout << n << endl
using namespace std;
int main(){
  int a, b, c;
  string s;
  cin >> a >> s;
  if(a>=3200) co(s);
  else co("red");
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define All(v) (v).begin(),(v).end()
int dy[8] = {-1,0,1,0,-1,1,1,-1};
int dx[8] = {0,-1,0,-1,1,1,-1,-1};
const int mod = 1000000007;
const int inf = mod*mod;
const int d5 = 100100;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int h,w;
    cin>>h>>w;
    string s[h];
    for(int i=0;i<h;i++)cin>>s[i];
    int dp[h][w];
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++)dp[i][j]=mod;
    }
    dp[0][0]=(s[0][0]=='.'?0:1);
    for(int y=0;y<h;y++){
        for(int x=0;x<w;x++){
            for(int i=0;i<2;i++){
                int ny=y+dy[i];
                int nx=x+dx[i];
                if(ny<0||nx<0||ny>=h||nx>=w)continue;
                dp[y][x]=min(dp[y][x],dp[ny][nx]+(s[y][x]=='#'&&s[ny][nx]=='.'));
            }
        }
    }
    cout<<dp[h-1][w-1]<<endl;
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <stdio.h>
#include <functional>
#include <cfloat>
#include <math.h>
#include <numeric>
#include <string.h>
#include <sys/time.h>
#include <random>


#define fs first
#define sc second

using namespace std;

typedef long long ll;
typedef unsigned int uint;
typedef pair<ll, ll> P;



int main(){
    string s;
    cin >> s;
    int n = s.size();

    bool res = true;
    for(int i = 0; i < n; i++){
        if(s[i] != s[n-i-1]){
            res = false;
        }
    }

    for(int i = 0; i < (n-1)/2; i++){
//        cout << i << " " << (n-1)/2-i-1 << endl;
        if(s[i] != s[(n-1)/2-i-1]){

            res = false;
        }
    }

    for(int i = (n+1)/2; i < n; i++){
//        cout << i << " " << n-(i-(n+1)/2)-1 << endl;
        if(s[i] != s[n-(i-(n+1)/2)-1]){
            res = false;
        }
    }

    if(res){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
def main():
    N, K = map(int, input().split())
    A = [int(x) - 1 for x in input().split()]

    way = []
    seen = [False for _ in [0] * (2 * 10 ** 5 + 1)]
    now = 0
    for _ in range(K):
        if seen[now]:
            loop_start = way.index(now)
            loop = way[loop_start:]
            K -= len(way[:loop_start])
            now = loop[K % len(loop)]
            break
        way.append(now)
        seen[now] = True
        now = A[now]
    print(now + 1)


if __name__ == '__main__':
    main()


Measured memory_bytes: 32240
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace __gnu_pbds;
using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;

typedef tree <ll, null_type, less <ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// order_of_key(val): returns the number of values less than val
// find_by_order(k): returns an iterator to the kth largest element (0-based)

#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define sz(a) (ll)(a.size())
#define endl "\n"

template <class Ch, class Tr, class Container>
basic_ostream <Ch, Tr> & operator << (basic_ostream <Ch, Tr> & os, Container const& x) 
{
    os << "{ ";
    for(auto& y : x) 
    {
        os << y << " ";
    }
    return os << "}";
}

template <class X, class Y>
ostream & operator << (ostream & os, pair <X, Y> const& p) 
{
    return os << "[" << p.ff << ", " << p.ss << "]";
}

const ll L = 1e5+5;

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

    return gcd(b, a%b);
}

ll modexp(ll a, ll b, ll c)
{   
    a%=c;

    ll ans = 1;

    while(b)
    {
        if(b&1)
        {
            ans = (ans*a)%c;
        }

        a = (a*a)%c;
        b >>= 1;
    }

    return ans;
}

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

    ll K, X;
    cin >> K >> X;

    for(ll i=X-K+1; i<=X+K-1; i++)
    {
        cout << i << " ";
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int k = scan.nextInt();
		int s = scan.nextInt();


		if(s <= 2) {
			for(int i = 0; i < n; i++) {
				if(i < k) {
					System.out.print(s + " ");
				}else {
					System.out.print((s+1) + " ");
				}
			}
		}else {
			for(int i = 0; i < n; i++) {
				if(i < k) {
					System.out.print(s + " ");
				}else {
					System.out.print((s-1) + " ");
				}
			}
		}
	}

}

Measured memory_bytes: 44296