akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
const int N = 15; 
int main()
{
	int n, s[N] = {0}, h[N] = {0}, c[N] = {0}, d[N] = {0};
	scanf("%d", &n);
	for(int i = 0; i < n; i++)
	{
		char k;
		int  p;
		scanf(" %c %d", &k, &p);
		if(k == 'S')
		{
			s[p]++;
		}
		else if(k == 'H')
		{
			h[p]++;
		}
		else if(k == 'C')
		{
			c[p]++;
		}
		else if(k == 'D')
		{
			d[p]++;
		}
	}
	for(int i = 1; i <= 13; i++)
	{
		if(s[i] == 0)
		{
			printf("S %d\n", i);
		}
	}
	for(int i = 1; i <= 13; i++)
	{
		if(h[i] == 0)
		{
			printf("H %d\n", i);
		}
	}
	for(int i = 1; i <= 13; i++)
	{
		if(c[i] == 0)
		{
			printf("C %d\n", i);
		}
	}
	for(int i = 1; i <= 13; i++)
	{
		if(d[i] == 0)
		{
			printf("D %d\n", i);
		}
	}
	return 0;

}


Measured memory_bytes: 2704
def run():
	N, T = (int(x) for x in input().split())
	cost = 1001
	for _ in range(N):
		c, t = (int(x) for x in input().split())
		if t <= T and cost > c:
			cost = c

	print(cost if cost <= 1000 else 'TLE')


if __name__ == '__main__':
	run()

Measured memory_bytes: 2940
import java.util.Scanner;

public class Main {
	static boolean isPalindrome(String s){
		for(int i = 0 ; i < s.length() ; ++i){
			int j = s.length() - 1 - i;
			if(s.charAt(i) != s.charAt(j)){
				return false;
			}
		}
		return true;
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String S = sc.next();
		int N = S.length();
		int M = (N - 1) / 2;
		boolean f = isPalindrome(S) & 
				    isPalindrome(S.substring(0 , M)) &
	    			isPalindrome(S.substring(M + 1));

		if(f){
			System.out.println("Yes");
		}else{
			System.out.println("No");			
		}
	}
}


Measured memory_bytes: 23764
#include <iostream>
#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 200010;

ll ans;
int cnt;
char s[N];

int main()
{
	scanf("%s", s);
	for (char* p = s; *p; ++p)
		if (*p == 'B')
			++cnt;
		else
			ans += cnt;
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <string.h>
#include <bits/stdc++.h>
#include<algorithm> 
using namespace std;
// main() is where program execution begins.



int main() {
long long N, K, P[5001], C[5001], maxsc = -1000000000000000000, sc, cnt, maxci = -1000000000000000000;

cin >> N >> K;

for (int i = 1; i <= N; ++i)
{
	cin >> P[i];
}

for (int i = 1; i <= N; ++i)
{
	cin >> C[i];
}

int indx;
for (int i = 1; i <= N; ++i)
{
	sc = 0;
	cnt = 1;
	indx = P[i];
	while(cnt <=K){
		sc = sc + C[indx];
		indx = P[indx];
		if(sc > maxsc)
			maxsc = sc;
		if(indx == P[i])
			break;
		cnt++;
	}
	//cout << "cnt " << cnt << endl;
	if (cnt < K)
	{
		if (sc >=0)
		{   long long tmp1, tmp2;
			tmp1 = sc * (K/cnt);
			int cnte = K%cnt;
			indx = P[i];
			if(tmp1 > maxsc)
			maxsc = tmp1;
			while(cnte > 0){
				tmp1 = tmp1 + C[indx];
				indx = P[indx];
				if (tmp1 > maxsc)
					maxsc = tmp1;
				cnte--;	 
			}

			tmp2 = sc*(K/cnt - 1);
			indx = P[i];
			if(tmp2 > maxsc)
				maxsc = tmp2;
			while(true){
				tmp2 = tmp2 + C[indx];
				indx = P[indx];
				if(tmp2 > maxsc)
					maxsc = tmp2;
				if(indx == P[i])
					break;
			}

		}
	}
}

cout << maxsc << endl;
return 0;
}


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

//typedef
//------------------------------------------
typedef long long LL;
typedef vector<LL> VL;
typedef vector<VL> VVL;
typedef vector<string> VS;
typedef pair<LL, LL> PLL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int MOD = 1000000007;

// grid
//--------------------------------------------
VL dx = {0, 1, 0, -1};
VL dy = {1, 0, -1, 0};
VL dx2 = {-1, 0, 1, -1, 1, -1, 0, 1};
VL dy2 = {-1, -1, -1, 0, 0, 1, 1, 1};

//debug
//--------------------------------------------
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

//IO accelerate
//--------------------------------------------
struct InitIO {
    InitIO() {
        cin.tie(nullptr);
        ios_base::sync_with_stdio(false);
        cout << fixed << setprecision(30);
    }
} init_io;

//template
//--------------------------------------------
template<typename T>
istream& operator >>(istream& is, vector<T>& vec) {
  for(T& x: vec) is >> x;
  return is;
}
template<typename T>
ostream& operator <<(ostream& os, const vector<T>& vec) {
  for(int i=0; i<vec.size(); i++){
    os << vec[i] << ( i+1 == vec.size() ? "" : "\t" );
  }
  return os;
}
template<typename T>
ostream& operator <<(ostream& s, const vector<vector<T>>& vv) {
	for (int i = 0; i < vv.size(); ++i) {
		s << vv[i] << endl;
	}
	return s;
}

// 多重vector
// auto dp=make_v<int>(4,h,w) みたいに使える
template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

// 多重vectorのためのfill
// fill_v(dp,0) みたいに使える
template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
  for(auto &e:t) fill_v(e,v);
}

//main code

int main(int argc, char const* argv[])
{
	double a,b,x;
	cin >> a >> b >> x;
	double ans;
	if (a*b/2.0 < x/a) {
		double bb = 2*(b - (x / (a*a)));
		dump(bb/a);
		ans = atan(bb/a);
	} else {
		double aa = 2*x/(a*b);
		dump(b/aa);
		ans = atan(b/aa);
	}
	cout << ans*180/PI << endl;
	return 0;
}


Measured memory_bytes: 384
while True:
    try:
        string = [input() for _ in range(8)]
        string = [int(l) for line in string for l in line] + [0]*32
        one = string.index(1)
        s = string[one:]
        ones = [[1, 8, 9], [8, 16, 24], [1, 2, 3],
                [7, 8, 15], [1, 9, 10], [8, 9, 17], [1, 7, 8]]
        ans = {0: "A", 1: "B", 2: "C", 3: "D", 4: "E", 5: "F", 6: "G"}
        for k, o in enumerate(ones):
            if all([s[o[0]], s[o[1]], s[o[2]]]):
                print(ans[k])
        input()
    except:
        break

Measured memory_bytes: 7604
#include<bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
using LL = long long;
const LL LINF = 1e18;
using namespace std;
#define COUT(v) cout<<(v)<<endl
#define CIN(n)  int(n);cin >> (n)
#define YES(n) cout<<((n)? "YES" : "NO")<<endl
#define Yes(n) cout<<((n)? "Yes" : "No")<<endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) <<endl

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)

#define FOREACH(x,a) for(auto& (x) : (a) )

#define ALL(obj) (obj).begin(),(obj).end()

#define P pair<int,int>
#define I vector<int>
#define S set<int>
#define pb(v) push_back(v)
#define V vector
#define rt return
#define rmsame(a) sort(ALL(a)),a.erase(unique(ALL(a)), a.end())
class Edge{
public:
    int from,to,value;
    Edge(int a,int b,int c){
        from = a;
        to = b;
        value = c;
    }
    Edge(int a,int b){
        from = a;
        to = b;
    }
};
int retrnd(int n){
     std::random_device rnd;
     std::mt19937 mt(rnd());
      std::uniform_int_distribution<> rand100(0, n);
      return rand100(mt);
}
int ruiseki[90010];
int main(){
    CIN(H);CIN(W);CIN(D);
    int px[90010],py[90010];
    REP(a,H){
        REP(b,W){
            CIN(w);
            px[w]=b;
            py[w]=a;
        }
    }
    for(int a = D+1;a <= H*W;a++){
        ruiseki[a]=ruiseki[a-D]+abs(px[a]-px[a-D])+abs(py[a]-py[a-D]);
    }
    CIN(Q);
    REP(a,Q){
        CIN(L);CIN(R);
        COUT(ruiseki[R]-ruiseki[L]);
    }
    return 0;
}


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

using namespace std;

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)

typedef long long ll;

int H, W;
ll L;
char c[128][128];
int dist[4][128][128]; // N E S W
int dy[]={-1,0,1,0}, dx[]={0,1,0,-1};

int convert(char ch){ return ch=='N'?0:ch=='E'?1:ch=='S'?2:3; }
char reconvert(int n){ return n==0?'N':n==1?'E':n==2?'S':'W'; }

void solve(int sy, int sx, int sd){
  int y=sy,x=sx,dir=sd;
  dist[dir][y][x] = 0;
  for(int step=1;;step++){
    int nd = dir;
    int ny = y+dy[nd], nx = x+dx[nd];
    while(ny<0||ny>=H||nx<0||nx>=W||c[ny][nx]=='#'){
      nd = (nd+1)%4;
      ny = y+dy[nd], nx = x+dx[nd];
    }

    if(dist[nd][ny][nx]!=-1){
      ll l = L-dist[nd][ny][nx];
      l %= (dist[dir][y][x] - dist[nd][ny][nx] + 1);
      rep(i,4) rep(j,128) rep(k,128){
	if(dist[i][j][k] != l + dist[nd][ny][nx]) continue;
	printf("%d %d %c\n", j+1, k+1, reconvert(i));
	return;
      }
    }
    y = ny, x = nx, dir = nd;
    dist[dir][y][x] = step;
    if(step==L){
      printf("%d %d %c\n", y+1, x+1, reconvert(dir));
      return;
    }    
  }
}

int main(){
  while(scanf("%d%d%lld", &H,&W, &L) && H+W+L){
    int sy, sx, sd;
    memset(dist, -1, sizeof(dist));
    rep(i,H){
      scanf("%s", c[i]);
      rep(j,W){
	if(c[i][j]=='#'||c[i][j]=='.') continue;
	sy = i, sx = j,	sd = convert(c[i][j]);
	c[i][j] = '.';
      }
    }
    solve(sy, sx, sd);
  }
  return 0;
}

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

using namespace std;

typedef long long ll;
const ll INF = 1LL<<60;

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

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

ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}

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

  int n, p;
  cin >> n >> p;

  vector<int> a(n);
  for(int i = 0; i < n; i++) cin >> a[i];

  int cnt_e = 0;
  int cnt_o = 0;
  for(int i = 0; i < n; i++){
    if(a[i]%2==0){
      cnt_e++;
    }else{
      cnt_o++;
    }
  }

  ll ans = 0;

  ans = modpow(2, cnt_e, 1e18) * modpow(2, max(cnt_o-1, 0), 1e18);

  if(p==1 && cnt_o == 0) ans = 0;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
n, m = map(int, input().split())
p = []
s = []
seikai = [0]*(n+1)
penalty = [0]*(n+1)

for i in range(m):
    a,b = input().split()#文字
    p.append(int(a))
    s.append(b)

for i in range(m):
    if s[i] == 'AC':
        seikai[p[i]] = 1
    elif s[i] == 'WA' and seikai[p[i]]==0:
        penalty[p[i]] = penalty[p[i]]+1

for i in range(n+1):
    penalty[i] = penalty[i] * seikai[i]

c = sum(seikai)
d = sum(penalty)

print(c, end=' ')
print(d)


Measured memory_bytes: 14924
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long MOD = 1000000007;

void solve(long long N, std::vector<long long> A){
    map<ll, ll> idealmp;
    for(ll i = 1; i < N; i++){
        ll cnt = abs((N-i) - (i-1));
        idealmp[cnt]++;
    }
    map<ll, ll> mp;
    for(auto a : A) mp[a]++;
    ll pos = 0;
    if(N % 2 == 0) pos = 1;
    ll ans = 1;
    for(ll i = pos; i <= N-1; i += 2){
        if(i == 0 && (mp[i] != 1)){
            ans = 0;
            break;
        }
        if((i > 0 && i < N-1) && mp[i] != 2){
            ans = 0;
            break;
        }
        ans *= (mp[i] % MOD);
        ans %= MOD;
    }
    cout << ans << endl;
    /*
    cout << "-- real --" << endl;
    for(auto itr = mp.begin(); itr != mp.end(); itr++){
        cout << itr->first << " " << itr->second << endl;
    }
    cout << "-- ideal --" << endl;
    for(auto itr = idealmp.begin(); itr != idealmp.end(); itr++){
        cout << itr->first << " " << itr->second << endl;
    }
    */
    return;
}

int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> A(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&A[i]);
    }
    solve(N, std::move(A));
    return 0;
}


Measured memory_bytes: 11160
<?php
list($n, $k) = ints();
//list($r, $s, $p) = ints();
list($s, $p, $r) = ints();
$t = str();

//o($n, $k);
//o($r, $s, $p);
//o($t);
$score = 0;
for($i = 0; $i<$k; $i++){
    $l[$i] = 0;
}
for($i = 0; $i < $n; $i++){
    $te = $t[$i];
    if($i < $k){
        $score+=$$te;
    }else{
        if($t[$i] != $t[$i-$k]){
            $score+=$$te;
            $l[$i%$k] = 0;
        }else{
            $l[$i%$k]++;
            if($l[$i%$k] % 2 == 0){
                $score+=$$te;
//                o($i);
            }
        }
    }
}
echo $score;
function str(){
  return trim(fgets(STDIN));
}
function ints(){
  return array_map("intval", explode(" ", trim(fgets(STDIN))));
}
function int(){
  return intval(trim(fgets(STDIN)));
}
function o(...$val){
    if(count($val)==1)$val = array_shift($val);
    $trace = debug_backtrace();
    echo $trace[0]['line'].")";
    if(is_array($val)){
        if(count($val) == 0){
            echo "empty array";
        }elseif(!is_array(current($val))){
            echo "array:";
            echo implode(" ", $val)."\n";
        }else{
            echo "array:array\n";
            foreach($val as $row){
                echo implode(" ", $row)."\n";
            }
        }
    }else{
        echo $val."\n";
    }
}

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

int main() {
  int n, x;
  cin >> n >> x;
  vector<int> m(n);
  for (int i = 0; i < n; i ++) {
    cin >> m.at(i);
  }
  sort(m.begin(), m.end());

  int count = n;
  for (int i = 0; i < n; i ++) {
    x -= m.at(i);
  }

  while (x >= m.at(0)) {
    count ++;
    x -= m.at(0);
  }

  cout << count << endl;
}


Measured memory_bytes: 256
// In The Name Of The Queen
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, k, R[N], rev[N];
pair < int , int > A[N], B[N];
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++)
        scanf("%d", &A[i].first), A[i].second = i;
    for (int i = 0; i < n; i ++)
        scanf("%d", &B[i].first), B[i].second = i;
    int cnt = 0;
    for (int i = 0; i < n; i ++)
        if (A[i].first > B[i].first)
            cnt ++;
    if (cnt > n - 2)
        return !printf("No\n");
    sort(B, B + n);
    sort(A, A + n);
    for (int i = 0; i < n; i ++)
        if (A[i].first > B[i].first)
            return !printf("No\n");
    for (int i = 0; i < n; i ++)
    {
        R[A[i].second] = B[i].second;
        rev[B[i].second] = A[i].second;
    }
    int __c = 1, iod = rev[0];
    while (iod)
        __c ++, iod = rev[iod];
    cnt = 0;
    for (int i = 0; i < n; i ++)
        if (A[i].second != B[i].second)
            cnt ++;
    int fail = 1;
    for (int i = 0; i < n - 1; i ++)
        if (A[i + 1].first <= B[i].first)
            fail = 0;
    if (fail && cnt == n && __c == n)
        return !printf("No\n");
    printf("Yes\n");
    return 0;
}

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

using namespace std;
using llong = long long;
using P = pair<llong, llong>;

#define BE(x) x.begin(), x.end()

const llong inf = llong(1e18)+7;
const llong mod = 1e9+7;

int main(){
	llong N;
	vector<llong> a;

	cin >> N;
	a.resize(N+1);
	for(int i = 1; i <= N; i++)
		cin >> a[i];

	llong ans = 0;
	for(int i = 1; i <= N; i++){
		if(i < a[i] && i == a[a[i]])
			ans++;
	}

	cout << ans << endl;



	return 0;
}

Measured memory_bytes: 1024
# -*- coding: utf-8 -*-
n,m = map(int, input().split())
ps = [input().split() for _ in range(m)]

wa = [0]*(n+1)
solve = [False for _ in range(n+1)]
for p,s in ps:
    p = int(p)
    if s=="AC":
        solve[p] = True
    else:
        if not solve[p]:
            wa[p] += 1

ra = 0
rw = 0
for i in range(1,n+1):
    if solve[i]:
        ra += 1
        rw += wa[i]
print(ra,rw)


Measured memory_bytes: 33904
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

#define MAX 1005

int sort[MAX];

int main(void) {

	int N, K;
	std::vector<int> p;

	cin >> N >> K;
	int data;
	int count = 0;
	//各果物の価格を標準入力で読み込む
	for (int i = 0; i < N; i++) {
		cin >> data;
		p.push_back(data);
		//cout << p[i] << " ";
	}

	//ソート
	std::sort(p.begin(), p.end());

	int sum = 0;
	for (int i = 0; i < K; i++) {
		sum += p[i];
		//cout << p[i] << " ";
	}

	cout << sum << endl;

	return 0;
}

Measured memory_bytes: 3164
#include<bits/stdc++.h>
using namespace std;
long long n;
long long a[10];
int main()
{
    long long ans=1e18;
    cin>>n;
    for(int i=1;i<=5;i++)
        cin>>a[i],ans=min(ans,a[i]);
    cout<<n/ans+(n%ans>0)+4<<endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#define INF 1000000007LL
using namespace std;

long long int inv(long long int x){
	long long int xpow[30], c[30];
	for(int i=0; i<30; i++){
		if(i==0){
			xpow[i]=x;
			c[i]=1;
		}else{
			xpow[i]=xpow[i-1]*xpow[i-1]%INF;
			c[i]=c[i-1]*2;
		}
	}
	long long int r=INF-2, xinv=1;
	for(int i=29;i>=0; i--){
		if(r>=c[i]){
			xinv=xinv*xpow[i]%INF;
		}
		r=r%c[i];
	}
	return xinv;
}

int main()
{
	long long int n, a[100001];
	long long int asum=0;
	scanf("%lld", &n);
	for(long long int i=0; i<=n; i++){
		scanf("%lld", &a[i]);
		asum=asum+a[i];
	}
	long long int m=asum-n*(n+1)/2;
	long long int k1=-1, k2;
	for(long long int i=0; i<=n; i++){
		if(a[i]==m && k1==-1){
			k1=i;
		}else if(a[i]==m){
			k2=i;
		}
	}
	long long int f[100001];
	for(long long int i=0; i<=n;i++){
		if(i==0){
			f[i]=1;
		}else{
			f[i]=i*f[i-1]%INF;
		}
	}
	if(n==1){
		printf("%d\n", 1);
		printf("%d\n", 1);
	}else{
		for(long long int k=1; k<=n+1; k++){
			if(k==1){
				printf("%lld\n", n);
			}else if(k==n+1){
				printf("%d\n", 1);
			}else{
				long long int ans=0;
				ans=(ans+2*f[n-1]%INF*inv(f[n-k])%INF*inv(f[k-1])%INF)%INF;
				if(n+k1-k2>=k-1){
					ans=(ans+INF-f[n+k1-k2]*inv(f[k-1])%INF*inv(f[n+k1-k2-k+1])%INF)%INF;
				}
				if(k<=n-1){
					ans=(ans+f[n-1]*inv(f[k])%INF*inv(f[n-k-1])%INF)%INF;
				}
				ans=(ans+f[n-1]*inv(f[k-2])%INF*inv(f[n-k+1])%INF)%INF;
				printf("%lld\n", ans);
			}
		}
	}
			
	return 0;
}


Measured memory_bytes: 2816
package main

import (
	"fmt"
	"sort"
)

func main() {
	var n int
	fmt.Scan(&n)
	
	var s string
	var p int
	keys := make([]string,n)
	rests := make(map[string]int, n)
	
	for i := 0; i < n; i++ {
		fmt.Scan(&s, &p)
		keys[i] = s + fmt.Sprintf("%03d",100 - p)
		rests[keys[i]] = i + 1
	}

	sort.Strings(keys)

	for i := range keys {
		fmt.Println(rests[keys[i]])
	}
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
int main(){
	string s;
	cin >> s;
	int l = s.size();
	for(int i = 0; i < l; i++)
		if(s[i] == 'C')
			for(int j = i; j <= l; j++)
				if(s[j] == 'F'){
					cout << "Yes";
					return 0;}
	cout << "No";
	return 0;}

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

using namespace std;

const int inf = 1e9;

int l[15];
int N, A, B, C;

int dfs(int cur, int a, int b, int c) {
    if (cur == N) {
        if (min({a, b, c}) > 0) {
            return abs(a - A) + abs(b - B) + abs(c - C) - 30;
        }
        else return inf;
    }

    int d0 = dfs(cur + 1, a, b, c);
    int d1 = dfs(cur + 1, a + l[cur], b, c) + 10;
    int d2 = dfs(cur + 1, a, b + l[cur], c) + 10;
    int d3 = dfs(cur + 1, a, b, c + l[cur]) + 10;

    return min(d0, min({d1, d2, d3}));
}

int main() {
    cin >> N >> A >> B >> C;
    for (int i = 0; i < N; i++) cin >> l[i];
    cout << dfs(0, 0, 0, 0) << '\n';
}

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

#define FASTIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long int

int main() {

    FASTIO;

    int n, k;
    cin >> n >> k;

    vector<int> stones(n);

    for (int i = 0; i < n; i++)
    {
        cin >> stones[i];
    }

    vector<bool> dp(k + 1);

    // dp[i] denotes that if a person starts with pill of i stones if he can win or not

    dp[0] = false; // preson loses if pill of 0 stones as he cant remove

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

        // dp[i] will be 1 if by playing optimally, the player taking the turn can make the other player 
        // to land on a losing state i.e dp[i-possible] = 0 , -> dp[i] = 1

        bool cur = 1;

        for (int stone : stones)
        {
            if (i - stone >= 0)
            {
                cur = cur & dp[i - stone];
            }
        }

        dp[i] = !cur;
    }

    if (dp[k]) cout << "First";
    else cout << "Second";
}


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

using namespace std;
#define N 200200


int v[N];
int n, x, y, cnt, i, ok, ok1, l, r;
int main(){
    cin >> n;
    for (i = 0; i < n; ++i){
        cin >> v[i];
    }
    ok1 = 0;
    for (l = 0; l < n; ++l){
        for (r = l; r < n; ++r){
            swap(v[l], v[r]);
            ok = 1;
            for (i = 1; i < n; ++i)
                if (v[i] < v[i - 1])
                    ok = 0;
            if (ok)
                ok1 = 1;
            swap(v[l], v[r]);

        }
    }
    if (ok1)
        cout << "YES";
    else
        cout << "NO";
    return 0;
}


Measured memory_bytes: 3644
N,M=map(int,input().split(' '))

m=[[] for i in range(N)]

for i in range(M):
  x,y=map(int,input().split(' '))
  m[x-1].append(y-1)
  m[y-1].append(x-1)

sign=[0]
signed_map=[-1]*N
signed_map[0]=1
while True:
  signed=sign
  sign=[]
  for s in signed:
    for room in m[s]:#サインされた場所から繋がってるとこを回る
      if signed_map[room]==-1:
        signed_map[room]=s+1
        sign.append(room)
  if sign==[]:break

print('Yes')
for ch in signed_map[1:]:
  print(ch)


Measured memory_bytes: 96560
l,r = gets.split.map(&:to_i)

if l % 2019 >= r % 2019 || r - l >= 2019
    puts 0
else
    ans = 2019
    l.upto(r-1) do |i|
        (i+1).upto(r) do |j|
            x = i * j % 2019
            ans = x if ans > x
        end
    end
    puts ans
end

Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define REPL(i,m,n) for(ll i=(ll)(m); i<(ll)(n); i++)
#define repl(i,n) REP(i,0,n)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

int main(){

  ll A, B;
  cin >> A;
  cin >> B;

  if ( ((B - 1) % (A - 1)) == 0 )
    cout << (B - 1) / (A - 1) << endl;
  else
    cout << ((B - 1) / (A - 1)) + 1 << endl;

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
vector<int64_t> prod_permutation(vector<int64_t> v,vector<int64_t> w){//v○wの計算(先にwで置換、その後vで置換)
    if(v.size()!=w.size()){
        cout << "error" << endl;
        return v;
    }else{
        vector<int64_t> ret;
        for(int i=0;i<v.size();i++){
            ret.push_back(v[w[i]]);
        }
        return ret;
    }
}
vector<int64_t> pow_permutation(vector<int64_t> v,int64_t N){//置換vをN乗した結果を返す。
    if(N%2==0){
        if(N==0){
            vector<int64_t> ret;
            for(int i=0;i<v.size();i++){
                ret.push_back(i);
            }
            return ret;
        }else{
            vector<int64_t> ret = pow_permutation(v,N/2);
            return prod_permutation(ret,ret);
        }
    }else{
        if(N==1){
            return v;
        }else{
            vector<int64_t> ret=pow_permutation(v,(N-1)/2);
            return prod_permutation(prod_permutation(v,ret),ret);
        }
    }
}
int main(){
    int64_t N;
    int64_t x[100000];
    int64_t M;
    int64_t K;
    int64_t a[100000];
    cin >> N;
    int64_t dx[100000];
    for(int i=0;i<N;i++){
        cin >> x[i];
        if(i!=0){
            dx[i-1]=x[i]-x[i-1];
        }
    }
    cin >> M >> K;
    for(int i=0;i<M;i++){
        cin >> a[i];
    }
    vector<int64_t> v;
    for(int i=0;i<N-1;i++){
        v.push_back(i);
    }
    for(int i=0;i<M;i++){
        int64_t tmp=v[a[i]-2];
        v[a[i]-2]=v[a[i]-1];
        v[a[i]-1]=tmp;
    }
    vector<int64_t> ret = pow_permutation(v,K);
    int64_t dx_permu[100000];
    for(int i=0;i<N-1;i++){
        dx_permu[i]=dx[ret[i]];
    }
    int64_t ans=x[0];
    for(int i=0;i<N-1;i++){
        cout << ans << endl;
        ans += dx_permu[i];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 55156
from collections import deque

n = int(input())
visit = [-1 for _ in range(n+1)]
friends = [[] for _ in range(n+1)]
for i in range(n-1):
    u, v, w = map(int, input().split())
    friends[u].append([v, w])
    friends[v].append([u, w])

q = deque([1])
visit[1] = 0
while q:
    position = q.popleft()
    for i, cost in friends[position]:
        if visit[i] < 0:
            visit[i] = visit[position] + cost
            q.append(i)

for i in visit[1:]:
    print(i%2)

Measured memory_bytes: 50108
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  
  string res;
  
  for (int i = 1; i <= 200; i++) {
    A = A - D*( (i+1) % 2 );
    C = C - B*( (i) % 2 );
    
    if (A <= 0) {
      res = "No";
      cout << res << endl;
      return 0;
      
    } else if (C <= 0){
      res = "Yes";
      cout << res << endl;
      return 0;
    }
  }
  
}

Measured memory_bytes: 3628
#include<iostream>
using namespace std;
int main(){
  string s,t;
  int i;
  bool b=true;
  cin>>s>>t;
  for(i=0;i<s.size();i++){
    if(s.at(i)!=t.at(i)){
      b=false;
    }
  }
  //cout<<b<<endl;
  if(b==true&&s.size()==t.size()-1){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
}

Measured memory_bytes: 3556
#include "bits/stdc++.h"

using namespace std;
typedef long long ll;
#define rep(i, j, n) for (int i = j; i < n; i++)
#define out(ans) cout << ans << endl;
const ll mod = 1e9 + 7;


int main(){

  int a,b,c;cin>>a>>b>>c;

  int sum=0;
  for(int i=1;a*i<=a*b;i++){
    if(a*i%b==c){
      out("YES");
      return 0;
    }
  }
  out("NO");

  return 0;
}


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

typedef long long ll;
typedef pair<int,int> ii;
typedef tree<ii,null_type,less<ii>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	ll A,B,N; cin>>A>>B>>N;
	cout<<A*min(B-1,N)/B<<"\n";
	return 0;
}

Measured memory_bytes: 3648
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define FOR(i, a, b) for(ll i = a; i < b; i++)
#define FORR(i, a, b)   for(ll i = a; i >= b; i--)
#define all(x) (x).begin(), (x).end()
#define MOD1 1000000007
#define MOD2 998244353
#define IOS std::ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define pb push_back
#define print(a) for(auto x : a)    cout<<x<<" "; cout<<"\n";
using namespace std;

void OFFLINE(){ 
    #ifndef ONLINE_JUDGE 
        freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); 
    #endif
}

int main(){

    IOS;
    // OFFLINE();
    //check for corner test cases

    int l, r, d;
    cin >> l >> r >> d;
    int ans = 0;

    for(int i = l; i <= r; i++)
        if(i % d == 0)  ans++;
    cout<<ans<<"\n";
    //check for corner test cases
    return 0;
}


Measured memory_bytes: 3608
import java.util.*;
public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    
    //条件１
    boolean j1 = false;
    if('A' == s.charAt(0)){
      j1 = true;
    }
    
    //条件２
    boolean j2 = false;
    for(int i = 2 ; i < s.length()-1 ; ++i){
      if('C' == s.charAt(i) && j2 == false){
        j2 = true;
      }else if('C' == s.charAt(i) && j2 == true){
        j2 = false;
        break;
      }
    }

    //条件３
    boolean j3 = false;
    for(int i = 0 ; i < s.length() ; ++i){
      if('A' == s.charAt(i)){
        j3 = true;
      }else if('C' == s.charAt(i)){
        j3 = true;
      }else if(Character.isUpperCase(s.charAt(i))==false){
        j3 = true;
      }else{
        j3 = false;
        break;
      }
    }
    
    if(j1&&j2&&j3){
      System.out.println("AC");
    }else{
      System.out.println("WA");
    }
    
  }
}

Measured memory_bytes: 35612
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define all(a) a.begin(), a.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;

int main(){

    int M, K;
    cin >> M >> K;

    if(M == 0){
        if(K == 0)cout << "0 0\n";
        else cout << "-1\n";
    } else if(M == 1){
        if(K == 0)cout << "1 1 0 0\n";
        else cout << "-1\n";
    } else {
        if(K >= (1 << M))cout << "-1\n";
        else {
            vector<int> ans(1 << (M + 1));
            int pos = 0;
            ans[pos++] = K;
            rep(i, 1 << M)if(i != K)ans[pos++] = i;
            ans[pos++] = K;
            for(int i = (1 << M) - 1; i >= 0; i--)if(i != K)ans[pos++] = i;
            rep(i, 1 << (M + 1))cout << ans[i] << (i == (1 << (M + 1)) - 1 ? '\n' : ' ');
        }
    }

}

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

using namespace std ;

int main() {
    long long n , m,i,j,k,rans,ans;
  //  cout << 'o' ;

    cin >> n >> m ;

  //  cout <<'p';

    long long a[100][100],b=0;
 //   cout << 'q' ;
    for(i=0;i<n;i++){
  //          cout << 's' ;
        for(j=0;j<m;j++){
    //            cout << 'r' ;
            cin >> a[i][j] ;
        }
    }
    for(i=0;i<n;i++){
        for(j=i+1;j<n;j++){
                ans= 0 ;
            for(k=0;k<m;k++){
                ans+= abs(a[i][k]-a[j][k]) * abs(a[i][k]-a[j][k]);
            }
          int y=sqrt(ans);
            if(y*y==ans)
                b++ ;
        }
    }

    cout << b ;




}


Measured memory_bytes: 256
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>

using namespace std;

//I imitated Ant Book version 1: P.84.

int n,q,com,x,y;
int rank[10000],parent[10000];

int find(int x){
	if(x == parent[x])return x;
	else{
		return parent[x] = find(parent[x]);
	}
}

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

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

	if(x == y)return;

	if(rank[x] < rank[y]){
		parent[x] = y;
	}else{
		parent[y] = x;
		if(rank[x] == rank[y])rank[x]++;
	}
}

int main(){

	scanf("%d %d",&n,&q);

	for(int i = 0; i < n; i++){
		rank[i] = 0;
		parent[i] = i;
	}

	for(int i = 0; i < q; i++){
		scanf("%d %d %d",&com,&x,&y);

		if(com == 1){
			if(isSame(x,y))printf("1\n");
			else{
				printf("0\n");
			}
		}else{
			if(isSame(x,y))continue;

			unite(x,y);
		}
	}

	return 0;
}

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

int solve(int bit1,int bit2,int n){
	vector<int> done(65536,1e9);
	queue<int> Q;
	Q.push(bit1);
	done[bit1] = 0;
	while( Q.size() ){
		int q = Q.front(); Q.pop();
		for(int i = 1 ; i < n ; i++){
			if( (q >> (i-1) & 3) == 0 || (q >> (i-1) & 3) == 3 ) continue;
			int nex = q^(3 << (i-1));
			if( done[nex] == 1e9 ){
				done[nex] = done[q] + 1;
				Q.push(nex);
			}
		}
	}
	return done[bit2];
}
int main(){
	int n,m;
	cin >> n >> m;
	int a = 0;
	for(int i = 0 ; i < n ; i++){
		int t; cin >> t;
		a = 2*a + t;
	}
	int b = 0;
	
	int l = 0;
	for(int i = 0 ; i < m ; i++){
		int t; cin >> t;
		while(t--) b = b * 2 + (i&1);
	}
	cout << min( solve(a,b,n), solve(a,b^((1<<n)-1),n) ) << endl;
}

Measured memory_bytes: 1480
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define rep(i, n) for(int i=0;i<n;++i)
#define rrep(i, n) for(int i=n;i>=0;--i)
const int inf=1e9+7;
const ll mod=1e9+7;
const ll mod1=998244353;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  int N;
  cin>>N;
  ll a[N];
  ll index=0;
  for(int i=0;i<N;++i) {
    cin>>a[i];
    if(abs(a[index])<abs(a[i])) index = i;
  }
  vector<pair<int, int> > ans;
  if(a[index]>0) {
    for(int i=0;i<N-1;++i) {
      while(a[i]>a[i+1]) {
        ans.push_back(mp(index, i+1));
        a[i+1] += a[index];
        if(abs(a[i+1])>abs(a[index])) index = i+1;
      }
    }
  }
  else {
    for(int i=N-1;i>0;--i) {
      while(a[i-1]>a[i]) {
        ans.push_back(mp(index, i-1));
        a[i-1] += a[index];
        if(abs(a[i-1])>abs(a[index])) index = i-1;
      }
    }
  }
  cout<<ans.size()<<endl;
  for(int i=0;i<ans.size();++i) cout<<ans[i].fi+1<<" "<<ans[i].se+1<<endl;
}



Measured memory_bytes: 3656
#include<cstdio>
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>


using namespace std;


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

#ifdef __BORLANDC__
	typedef __int64 ll;
#else
	typedef long long ll;
#endif


int main()
{
	vector<int> a;
	vector<int> b;
	
	
	int w,h;
	
	cin>>w>>h;
	
	rep(i,w)
	{
		int t;
		cin>>t;
		a.push_back(t);
	}
	
	rep(i,h)
	{
		int t;
		cin>>t;
		b.push_back(t);	
	}
	
	
	int ai = 0;
	int bi = 0;
	
	int inf = 1000000000;
	
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	
	ll ans = 0;
	
	while(1)
	{
		int ak = ai == a.size() ? inf : a[ai];
		int bk = bi == b.size() ? inf : b[bi];
		
		
		if(ak==inf && bk==inf)break;
		if(ak<bk)
		{
			ai++;
			ans += (b.size()-bi+1)*ak;		
		}else
		{
			bi++;
			ans += (a.size()-ai+1)*bk;
		}
	}
	
	cout<<ans<<endl;

}




Measured memory_bytes: 1528
import java.util.Scanner;

import java.util.List;
import java.util.ArrayList;;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		while (true) {
			List<int[]> numList = new ArrayList<int[]>();
			int cnt = 0;
			String tmp = scan.nextLine();
			int n, x;
			n = Integer.parseInt(tmp.split(" ")[0]);
			x = Integer.parseInt(tmp.split(" ")[1]);
			if (n == 0 && x == 0) {
				break;
			}
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					for (int t = 1; t <= n; t++) {
						if (i + j + t == x && i != j && i != t && j != t) {
							if(check(i,t,j,numList) && check(i,j,t,numList) && check(t,i,j,numList) && check(t,j,i,numList) && check(j,i,t,numList) && check(j,t,i,numList)){
								int[] tmpNums = new int[3];
								tmpNums[0] = i;
								tmpNums[1] = j;
								tmpNums[2] = t;
								numList.add(tmpNums);
							}
						}
					}

				}
			}
			System.out.println(numList.size());
		}
	}

	public static boolean check(int i,int j ,int t,List<int[]> numList){
		for (int s = 0; s < numList.size(); s++) {
			int[] tmp = new int[3];
			tmp = numList.get(s);
			if (tmp[0] == i && tmp[1] == j && tmp[2] == t) {
				return false;
			}
		}
		return true;
	}

}



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

int gcd(int x,int y){
  if(y==0){
    return x;
  }
  return gcd(y,x%y);
}

int main() {
  long long int a,b;
  cin>>a>>b;
  int c=gcd(a,b);
  cout<<a*b/c<<endl;
}

Measured memory_bytes: 256
package main

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

var sc = bufio.NewScanner(os.Stdin)

func Scan() string {
	sc.Scan()
	return sc.Text()
}
func iScan() int {
	n, _ := strconv.Atoi(Scan())
	return n
}
func fScan() float64 {
	n, _ := strconv.ParseFloat(Scan(), 64)
	return n
}
func stringToInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}
func SScan(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = Scan()
	}
	return a
}
func iSScan(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = iScan()
	}
	return a
}
func abs(x int) int {
	if x < 0 {
		x = -x
	}
	return x
}
func larger(a, b int) int {
	if a < b {
		return b
	} else {
		return a
	}
}
func smaller(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}
func max(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x < a[i] {
			x = a[i]
		}
	}
	return x
}
func min(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x > a[i] {
			x = a[i]
		}
	}
	return x
}
func sum(a []int) int {
	x := 0
	for _, v := range a {
		x += v
	}
	return x
}

var mod int = 1000000007

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, mod)
	sc.Split(bufio.ScanWords)
	n := iScan()
	m := iScan()
	lrc := make([][]int, m)
	for i := 0; i < m; i++ {
		lrc[i] = []int{iScan() - 1, iScan() - 1, iScan()}
	}
	sort.SliceStable(lrc, func(i, j int) bool { return lrc[i][1] < lrc[j][1] })
	dp := make([]int, n)
	for i := 1; i < n; i++ {
		dp[i] = mod * mod
	}
	for i := 1; i < n; i++ {
		for len(lrc) != 0 {
			if lrc[0][1] == i {
				dp[i] = smaller(dp[lrc[0][0]]+lrc[0][2], dp[i])
				lrc = lrc[1:]
			} else {
				break
			}
		}
		for j := i - 1; j > 0; j-- {
			if dp[j] > dp[i] {
				dp[j] = dp[i]
			} else {
				break
			}
		}
	}
	if dp[n-1] == mod*mod {
		fmt.Println(-1)
	} else {
		fmt.Println(dp[n-1])
	}
}


Measured memory_bytes: 9776
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; i++)
#define RFOR(i, a, n) for (ll i = (ll)n - 1; i >= (ll)a; i--)
#define rep(i, n) FOR(i, 0, n)
#define rrep(i, n) RFOR(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define bra(first, second) '(' << first << ',' << second << ')'
//constexpr ll MOD = 1000000007;
constexpr ll MOD = 998244353;
ll INF = 1001001001001001001;
long double EPS = 1e-9;
long double PI = 3.141592653589793238;
template <typename T>
void remove(std::vector<T> &vector, unsigned int index)
{
   vector.erase(vector.begin() + index);
}

using Graph = vector<vector<pair<ll,ll>>>;

// MOD確認

template <class T>
class SegmentTree{
  ll N;
  vector<T> data;
  vector<T> lazy;
  T def;
  function<T(T,T)> operation;
  function<T(T,T)> update;
  public:
  SegmentTree(size_t _N,T _def,function<T(T,T)> _operaition,function<T(T,T)> _update):def(_def),operation(_operaition),update(_update){
          N = 1;
          while(N < _N){
              N *= 2;
          }
          data = vector<T>(2*N-1,def);
          lazy = vector<T>(2*N-1,0);
  }

  void change(ll i,ll x){
      i += N-1;
      data[i] = update(data[i],x);
      while(i > 0){
          i = (i-1)/2;
          data[i] = operation(data[i*2+1],data[i*2+2]);
      }
  }

  void eval(ll k,ll l,ll r){
      if(lazy[k] != 0){
          data[k] += lazy[k];
          if(r - l > 1){
              lazy[k*2+1] += (lazy[k] / 2);
              lazy[k*2+2] += (lazy[k] / 2);
          }
          lazy[k] = 0;
      }
  }

  void add(ll a,ll b,ll x,ll k = 0,ll l = 0,ll r = -1){
      if(r < 0) r = N;
      eval(k,l,r);
      if(b <= l || r <= a) return;
      if(a <= l && r <= b){
          lazy[k] += (r-l) * x;
          eval(k,l,r);
      }else{
          add(a,b,x,k*2+1,l,(l+r)/2);
          add(a,b,x,k*2+2,(l+r)/2,r);
          data[k] = data[k*2+1] + data[k*2+2];
      }
  }
  
  T query(ll a,ll b,ll k = 0,ll l = 0,ll r = -1){
      if(r < 0) r = N;
      eval(k,l,r);
      if(b <= l || r <= a) return def;
      if(a <= l && r <= b){
          return data[k];
      }else{
          T c1 = query(a,b,k*2+1,l,(l+r)/2);
          T c2 = query(a,b,k*2+2,(l+r)/2,r);
          return operation(c1,c2);
      }
  }

  T operator[](ll i){
      return lazy[i+N-1];
  }

  T oper(ll i){
      return data[i+N-1];
  }

};


ll N,K;
pair<ll,ll> A[20];


int main(){
   cin >> N >> K;
   rep(i,K) cin >> A[i].first >> A[i].second;
   auto f = [](ll a,ll b){return (a+b) % MOD;};
   auto g = [](ll a,ll b){return b;};
   SegmentTree<ll> ST(N+10,0,f,g);
   ST.change(0,1LL);
   rep(i,N){
      rep(j,K){
         if(i + A[j].first > N - 1) continue;
         else {
            ST.add(i+A[j].first,min(N-1,i+A[j].second)+1,ST.query(i,i+1));
         }
      }
   }
   cout << ST.query(N-1,N) % MOD << endl;
}

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

// #define int long long
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

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

const ll INF = 1e15;
const int MOD = 1e9+7;
const ll LINF = 1e18;

ll n;
vector<pll> G[100005];
ll dist[100005];


void dijkstra(ll s){
  fill(dist,dist+n,LINF);
  dist[s]=0;
  priority_queue<pll, vector<pll>, greater<pll>> q;
  q.emplace(0,s);
  while(!q.empty()){
    pll v=q.top(); q.pop();
    if(dist[v.second]<v.first) continue;
    for(auto nv: G[v.second]){
      if(dist[nv.first]>dist[v.second]+nv.second){
        dist[nv.first]=dist[v.second]+nv.second;
        q.emplace(dist[nv.first],nv.first);
      }
    }
  }
}

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  cin>>n;
  rep(i,n-1){
    ll a,b,c; cin>>a>>b>>c;
    a--,b--;
    G[a].emplace_back(b,c);
    G[b].emplace_back(a,c);
  }
  
  ll q,k; cin>>q>>k;
  k--;
  dijkstra(k);
  vll x(q),y(q);
  rep(i,q){
    cin>>x[i]>>y[i];
    x[i]--,y[i]--;
  }
  
  rep(i,q){
    cout<<dist[x[i]]+dist[y[i]]<<endl;
  }
  
}

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

int main()
{
  int n;
  cin>>n;
  int cnt=0,a,b;
  while(n--)
  {
    cin>>a>>b;
    if(a==b)
      cnt++;
    if(cnt==1 || cnt==2)
    {
      if(a!=b)
        cnt=0;
    }
  }
  if(cnt>=3)
    cout<<"Yes";
  else 
    cout<<"No";
    
  return 0;
}

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

/*
code credits : ਜ਼ੈਲਦਾਰ
dashan jot singh
*/
using namespace std;
#define ll long long int
#define fast ios_base::sync_with_stdio(0), cin.tie(NULL), cout.tie(NULL)
#define pb push_back
#define mp make_pair
#define inf LLONG_MAX
#define pl pair<ll,ll>
#define loop(n) for(ll i=0;i<n;i++)

void solve(){
    ll x,y,a,b,c;
    cin>>x>>y>>a>>b>>c;
    ll p[a],q[b],r[c];
    loop(a) cin>>p[i];
    loop(b) cin>>q[i];
    loop(c) cin>>r[i];
    priority_queue<ll, vector<ll>, greater<ll>> pq;
    sort(p,p+a);
    reverse(p,p+a);
    sort(q,q+b);
    reverse(q,q+b);

    loop(x) pq.push(p[i]);
    loop(y) pq.push(q[i]);
    loop(c) {
    	if(pq.top()<r[i]){
    		pq.pop();
    		pq.push(r[i]);
    	}
    }
    ll ans=0;
    while(!pq.empty()){
    	ans+=pq.top();
    	pq.pop();
    }
    cout<<ans<<"\n";

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

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

int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    cin >> N;
    vector<bool> color(8, false);
    int rate, cnt = 0;
    for(int i = 0; i < N; i++)
    {
        cin >> rate;
        if(rate < 400)  color[0] = true;
        else if(rate < 800)  color[1] = true;
        else if(rate < 1200) color[2] = true;
        else if(rate < 1600) color[3] = true;
        else if(rate < 2000) color[4] = true;
        else if(rate < 2400) color[5] = true;
        else if(rate < 2800) color[6] = true;
         else if(rate < 3200) color[7] = true;
        else if(rate >= 3200)   cnt++;
    }
    cout<<max(accumulate(color.begin(),color.end(),0),1)<<" "<<accumulate(color.begin(),color.end(),0)+cnt<<endl;
	return 0;
}

Measured memory_bytes: 3604
use std::cmp;
use std::collections::HashMap;
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! {
        n: usize,
        k: usize,
        s: chars
    }

    let mut ans = 0;

    let mut peoples: Vec<usize> = Vec::new();

    let mut sakadachi = true;
    if s[0] == '0' {
        peoples.push(0);
        sakadachi = false;
    }
    let mut tmp = 0;
    for i in 0..s.len() {
        if sakadachi {
            if s[i] == '0' {
                peoples.push(tmp);
                sakadachi = false;
                tmp = 1;
            } else {
                tmp += 1;
            }
        } else {
            if s[i] == '1' {
                peoples.push(tmp);
                sakadachi = true;
                tmp = 1;
            } else {
                tmp += 1;
            }
        }
    }
    peoples.push(tmp);
    if s[s.len() - 1] == '0' {
        peoples.push(0);
    }

    let mut people_cum_sum = vec![0; peoples.len() + 1];
    for i in 1..peoples.len() + 1 {
        people_cum_sum[i] = people_cum_sum[i - 1] + peoples[i - 1];
    }

    let section = k * 2 + 1;
    for i in 1..people_cum_sum.len() {
        if i % 2 == 1 {
            let sub = if i < section { 0 } else { i - section };
            let sakadachi_num = people_cum_sum[i] - people_cum_sum[sub];

            if ans <= sakadachi_num {
                ans = sakadachi_num;
            }
        }
    }

    println!("{}", ans);
}

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: 10620