akhauriyash/Code-Regression huggingface dataset:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt, pi
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N, M = getNM()
que = []
for i in range(M):
    a, b = getNM()
    que.append([a - 1, b - 1])
ball = [1] * N
red = [0] * N
red[0] = 1

for a, b in que:
    ball[b] += 1
    if red[a] == 1:
        red[b] = 1
    ball[a] -= 1
    if ball[a] == 0:
        red[a] = 0
print(sum(red))

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

#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define eb emplace_back
#define rep(i, a, b) for (long i = (a); i <= (b); ++i)
#define per(i, a, b) for (long i = (a); i >= (b); --i)
#define mmst(v) memset(v, 0, sizeof(v))

template<typename T1,typename T2> inline void chmin(T1 & a, T2 b) { if (a > b) a = b; }
template<typename T1,typename T2> inline void chmax(T1 & a, T2 b) { if (a < b) a = b; }

const long kMax2 = 109;
const long kMax3 = 1009;
const long kMax4 = 10009;
const long kMax5 = 100009;
const long kMax6 = 1000009;
const long kMax9 = 1000000010;
const long kInfI = 0x3F3F3F3F;
const float kInfF = 1e15;
const long long kMod = 1000000007;

const long long kMAX = 1000000000;

using namespace std;
using ll = long long;

inline int readInt() {
  char c = getchar();
  while(!isdigit(c) && c != '-') c = getchar();
  int sigma = 1;
  if (c == '-') {
    sigma = -1;
    c = getchar();
  }
  int x = 0;
  while (isdigit(c)) {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return x * sigma;
}

template <class T>
void PrintVector(const vector<T> & v) {
  for (const auto & e: v) {
    cout << e << endl;
  }
}

template <class T>
void PrintVector(const vector<T> & v, int n) {
  rep(i, 0, n - 1) {
    cout << v[i] << endl;
  }
}

int main() {
  long n, m, k, x, y, a, b;
  string s;
  ll ans;
  cin >> n >> s;
  if (n % 2 != 0) { cout << "No" << endl; return 0; }
  rep(i, 0, n / 2 - 1) {
    if (s[i] != s[n / 2 + i]) { cout << "No" << endl; return 0; }
  }
  cout << "Yes" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>

#define REP(i, a, b) for ( int i = (a); i < (b); i++ )
#define REVREP(i, a, b) for ( int i = (a); i >= (b); i--)
#define DEBUG_INT(var) printf("the value of "#var" is %d\n", var)
#define PRINT_ARRAY(name, i) printf("the value of "#name"[%d] is %d\n", (i), name[(i)])
#define DEBUG_ARRAY(name, begin, end) REP(i, begin, end) PRINT_ARRAY(name, i)

using namespace std;

int N, K, Q;
int C[100005];

int main(void) {
    scanf("%d %d %d", &N, &K, &Q);

    REP(i, 0, Q) {
    	int A;
    	scanf("%d", &A);
    	C[A - 1]++;
    }

    REP(i, 0, N) {
    	if (K - (Q - C[i]) > 0) puts("Yes");
    	else puts("No");
    }

	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>

using namespace std;


int main()
{
    size_t M = 1000000000 + 7;

    size_t S;
    cin >> S;

    vector<size_t> c(S+1, 0);    // c[i] = i+1 での組み合わせ数 mod M

    for (int i = 3; i <= S; ++i)
    {
        c[i] = 1;
        for (int j = 3; j <= (i-3); ++j)
        {
            c[i] = (c[i] + c[j]) % M;
        }
    }

    cout << c[S] << endl;

    return 0;
}


Measured memory_bytes: 3640
/*** author: yuji9511 ***/
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define rep(i,m,n) for(int i=(m);i<(n);i++)
#define rrep(i,m,n) for(int i=(m);i>=(n);i--)
#define printa(x,n) for(int i=0;i<n;i++){cout<<(x[i])<<" \n"[i==n-1];};
void print() {}
template <class H,class... T>
void print(H&& h, T&&... t){cout<<h<<" \n"[sizeof...(t)==0];print(forward<T>(t)...);}
vector<int> divisor(int M){
    vector<int> dd;
    for(int i = 1; i * i <= M; i++){
        if(M % i == 0){
            dd.push_back(i);
            if(i * i != M) dd.push_back(M / i);
        }
    }
    sort(dd.begin(), dd.end());
    return dd;
}

int num[1000010] = {};

void solve(){
    int N;
    cin >> N;
    int A[200010];
    rep(i,0,N) cin >> A[i];
    int ans = 0;
    rep(i,0,N) num[A[i]]++;
    rep(i,0,N){
        vector<int> div = divisor(A[i]);
        bool ok = true;
        for(auto &e: div){
            if(e == A[i]){
                if(num[e] > 1){
                    ok = false;
                    break;
                }
            }else{
                if(num[e] > 0){
                    ok = false;
                    break;
                }
            }
        }
        if(ok) ans++;
    }
    print(ans);
}

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


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

int main(){
    long long ans=0,sum=0;
    int n;
    cin >>n;

    //string s;
    vector<char> sarray(10);
    map<vector<char>,long long> sames;
    char c;

    for (int i = 0; i < n; i++){
        for (int j = 0; j < 10; j++){
            cin >> c;
            sarray[j]=c;
        }

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

        sames[sarray]++;
        /*
        for (int j = 0; j < 10; j++)
        {
            cout << sarray[i][j];
        }
        cout << endl;
        */
    }
    
    long long add=0;
    for(auto p : sames){
        
        if(p.second < 2){
            add=0;
        }else{
            add = ((p.second)*(p.second-1))/2;
        }

        ans += add;
    }
    


    //cout <<fixed<<setprecision(16)<< << endl;
    cout << ans << endl;

    //if(flag==1)cout << "Yes" <<endl;
    //else cout << "No" <<endl;
    
    return 0;
}


Measured memory_bytes: 11136
s = input()
if (int(s[:2]) >= 13 or s[:2] == '00') and (int(s[2:4]) >= 13 or s[2:4] == '00'):
    print('NA')
elif 0 < int(s[:2]) <= 12 and 0 < int(s[2:4]) <= 12:
    print('AMBIGUOUS')
elif 0 < int(s[:2]) <= 12:
    print('MMYY')
else:
    print('YYMM')

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

int main(){
    string s;
    cin >> s;
    string s_1 = s.substr(1,s.size()-2);
    int a = s_1.size();
    cout << s[0] << a << s[s.size()-1] << endl;

    return 0;
}

Measured memory_bytes: 256
class UFTree
  def initialize(n)
    @parent = (0...n).to_a
    @rank = Array.new(n, 0)
  end
     
  def find(x)
    return x if @parent[x] == x
    return @parent[x] = find(@parent[x])
  end
     
  def unite(a, b)
    a = find(a)
    b = find(b)
    return if a == b
    if @rank[a] < @rank[b]
      @parent[a] = b
    else
      @parent[b] = a
      @rank[a] += 1 if @rank[a] == @rank[b]
    end
  end
end
    
def smaller(a, b)
  a < b ? a : b
end
    
N = gets.to_i
G = []
(0...N).each do |i|
  a, b = gets.split.map(&:to_i)
  G << [a, b, i]
end

Q = []
H = G.sort{|a, b| a[0] <=> b[0]}
H.zip(H.drop(1)).take(N - 1).each do |a, b|
  Q << [a[2], b[2], smaller((a[0] - b[0]).abs, (a[1] - b[1]).abs)]
end
     
J = G.sort{|a, b| a[1] <=> b[1]}
J.zip(J.drop(1)).take(N - 1).each do |a, b|
  Q << [a[2], b[2], smaller((a[0] - b[0]).abs, (a[1] - b[1]).abs)]
end

tree = UFTree.new(N)
cost = 0
n = 0
Q.sort!{|a, b| a[2] <=> b[2]}.each do |a, b, c|
  break if n == N
  next if tree.find(a) == tree.find(b)
  cost += c
  tree.unite(a, b)
  n += 1
end
     
puts cost


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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using ld = long double;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

const int64 mod = 1e9+7;

int main(void){
	int64 s;
	cin >> s;
	int32 cnt = 1;
	map<int64, int64> mp;
	mp[s] = 1;
	while(1){
		if(s%2){
			s = s*3+1;
		}else{
			s = s/2;
		}
		cnt++;
		if(mp[s]){
			cout << cnt << endl;
			return 0;
		}
		mp[s] = cnt;
	}
}


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

using namespace std;
typedef long long ll;

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

  int x; cin >> x;

  if (x < 1200) cout << "ABC" << "\n";
  else cout << "ARC" << "\n";
}


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

int main() {
    int N;
    cin >> N;
    map<string, ll> ang;
    for (int i = 0; i < N; i++) {
        string S;
        cin >> S;
        sort(S.begin(), S.end());
        ang[S]++;
    }

    ll sum = 0;
    for (auto p : ang) {
        ll n = p.second;
        sum += n * (n - 1) / 2;
    }

    cout << sum << endl;

    return 0;
}

Measured memory_bytes: 11136
#ABC079C
import copy
H,W=map(int,input().split())
C=[list(map(int,input().split())) for _ in range(10)]
A=[list(map(int,input().split())) for _ in range(H)]
def DP(i,check,x):
    s=C[i][1]
    for c in range(10):
        if c!=i and check[c]!=1 and C[i][c]<C[i][1]:
            t=copy.deepcopy(check)
            t[c]=1
            s=min(s,C[i][c]+DP(c,t,x))
    return x+s
B=[0]*10
for i in range(10):
    if i!=1:
        B[i]=DP(i,[1 if t==1 or t==i else 0 for t in range(10)],0)
D=[0]*10
for h in range(H):
    for w in range(W):
        if A[h][w]!=-1:
            D[A[h][w]]+=1
print(sum([B[i]*D[i] for i in range(10)]))

Measured memory_bytes: 3808
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
#define ll long long
ll maxx=1e9;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll x;
    cin>>x;
    for(ll a=-120;a<=120;a++)
        for(ll b=-120;b<=120;b++)
        {
            ll l=a*a*a*a*a,r=b*b*b*b*b;
            if(l-r==x)
            {
                cout<<a<<" "<<b<<'\n';
                return 0;
            }
        }
    return 0;
}


Measured memory_bytes: 3652
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <utility>
#include <set>
#include <stack>
#include <climits>
#include <cmath>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define rep1(i,n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
#define reps(i,s,n) for(int i=s, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define MEMSET(v, h) memset((v), h, sizeof(v))
typedef long long ll;
const char sp = ' ';


using namespace std;

int main(void){
    ll N;
    string S;
    cin>>N>>S;
    ll r=0, g=0, b=0;
    rep(i, N){
        if(S[i]=='R') r++;
        else if(S[i]=='G') g++;
        else if(S[i]=='B') b++;
    }
    ll count=r*g*b;
    rep(i, N) rep1(d, (N-1-i)/2){
        //cout<<count<<endl;;
        if(S[i]!=S[i+d] && S[i+d]!=S[i+2*d] && S[i]!=S[i+2*d]) count--;
    }
    cout<<count<<endl;
    return 0;
}


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

int main(){
    string s,t;
    cin >> s >> t;
    for(int i = 0; i < s.size(); i++){
        if(s[i] != t[i]){
            cout << "No" << endl;
            return 0;
        }

    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 3640
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <set>
const int N = 2e5 + 5; 
const int INF = 1e9; 
using namespace std;

int n, m, p[N], val[N], cnt[N]; 
char s[N]; 

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

struct SegTree
{
	struct Tree { int mx; } t[N << 2];
	void build(int p, int l, int r)
		{
			if(l == r) { t[p].mx = 1 - INF; return; }
			int mid = (l + r) >> 1; 
			build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
			t[p].mx = max(t[p << 1].mx, t[p << 1 | 1].mx); 
		}
	int query(int p, int l, int r, int ql, int qr)
		{
			if(ql <= l && r <= qr) return t[p].mx; 
			int mid = (l + r) >> 1; int ans = -INF; 
			if(ql <= mid) ans = query(p << 1, l, mid, ql, qr); 
			if(mid < qr) ans = max(ans, query(p << 1 | 1, mid + 1, r, ql, qr)); 
			return ans; 
		}
	void modify(int p, int l, int r, int k, int x)
		{
			if(l == r) return (void) (t[p].mx = x); 
			int mid = (l + r) >> 1; 
			if(k <= mid) modify(p << 1, l, mid, k, x); 
			else modify(p << 1 | 1, mid + 1, r, k, x); 
			t[p].mx = max(t[p << 1].mx, t[p << 1 | 1].mx); 
		}
} Odd, Even; 

bool check(int mx, int t)
{
	if(t < 0) return 0;
	if(t & 1) return Odd.query(1, 1, n, mx, n) >= t;
	else return Even.query(1, 1, n, mx, n) >= t; 
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("cpp.in", "r", stdin); 
#endif
	n = read <int> ();
	for(int mx = 0, i = 1; i <= n; i++)
	{
		p[i] = read <int> (); 
		if(p[i] > mx) val[i] = 2, mx = p[i];
		else val[i] = 1; 
	}
	Odd.build(1, 1, n); 
	for(int mx1, mx2, i = n; i >= 1; i--)
	{
		mx1 = Odd.query(1, 1, n, p[i], n), mx2 = Even.query(1, 1, n, p[i], n); 
		if(val[i] & 1) Odd.modify(1, 1, n, p[i], mx2 + val[i]), Even.modify(1, 1, n, p[i], mx1 + val[i]); 
		else Odd.modify(1, 1, n, p[i], mx1 + val[i]), Even.modify(1, 1, n, p[i], mx2 + val[i]); 
	}
	for(int i = n; i >= 1; i--) cnt[i] = cnt[i + 1] + val[i] - 1; 
	int cntx = 0, cnty = 0, mxx = 0, mxy = 0; 
	for(int i = 1; i <= n; i++)
	{
		Odd.modify(1, 1, n, p[i], 1 - INF), Even.modify(1, 1, n, p[i], 0); 
		if(check(mxy, cntx + cnt[i + 1] - cnty + (p[i] > mxx))) s[i] = '0', cntx += (p[i] > mxx), mxx = max(mxx, p[i]); 
		else if(check(max(mxx, p[i]), cnty + cnt[i + 1] - cntx - (p[i] > mxx))) s[i] = '0', cntx += (p[i] > mxx), mxx = max(mxx, p[i]); 
		else s[i] = '1', cnty += (p[i] > mxy), mxy = max(mxy, p[i]); 
	}
	if(cntx != cnty) puts("-1");
	else printf("%s\n", s + 1); 
	return 0;
}


Measured memory_bytes: 10320
#define rep(i, N) for(int (i) = 0; (i) < (N); (i) ++)
#define rep2(i, N, s) for(int (i) = (s); (i) < (N) + (s); (i) ++)
#define rrep(i, N) for(int (i) = (N) - 1; (i) >= (0); (i) --)
#define rrep2(i, N, s) for(int (i) = (s); (i) >= (s) - (N) + 1; (i) --)
#define INF 1e9

#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

typedef long long ll;
typedef  pair<int, int> pint;

int main(){
    int N, M, X, Y;
    cin >> N >> M;
    cin >> X >> Y;
    int x_max = -100;
    rep(i, N){
        int x;
        cin >> x;
        x_max = max(x, x_max);
    }
    int y_min = 100;
    rep(i, M){
        int y;
        cin >> y;
        y_min = min(y_min, y);
    }
    string ans = "No War";
    int z = x_max + 1;
    if(z > y_min){
        ans = "War";
    }

    for(; z <= y_min;  z++){
        if(!(z <= Y && z > X)){
            ans = "War";
            break;
        }
    }
    cout << ans << endl;


    return 0;
}


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

int main() {

    int a, b, c, d, e, f;
    cin >> a >> b >> c >> d >> e >> f;

    double max_m = 0;
    int max_beaker = 100;
    int max_s = 0;
    for (int i = 0; a * 100 * i <= f; ++i) {
        int wA = i * a * 100;
        for (int j = 0; wA + b * 100 * j <= f; ++j) {
            int wB = j * 100 * b;
            int w = wA + wB;
            if (0 == w || f < w) continue;
            for (int k = 0; w + (c * k) <= f; ++k) {
                int sC = k * c;
                for (int l = 0; w + sC + (d * l) <= f; ++l) {
                    int sD = d * l;
                    int s = sC + sD;
                    if ((100 * s <= e * w)) {
                        int acc = w + s;
                        double m = (double)s / (double)acc;
                        if (max_m <= m) {
                            max_m = m;
                            max_beaker = acc;
                            max_s = s;
                        }
                    }
                }
            }
        }
    }
    cout << max_beaker << " " << max_s << endl;
    return 0;
}


Measured memory_bytes: 256
H, W = map(int, input().split())
grid = []

for i in range(H):
    row = list(input())
    if "#" in row:
        grid.append(row)

h = len(grid)
for j in range(W):
    cnt = 0
    for i in range(h):
        if grid[i][j] == "#":
            cnt += 1
    if cnt <= 0:
        for i in range(h):
            grid[i][j] = "x"

for i in range(h):
    row = ""
    for j in range(W):
        if grid[i][j] != "x":
            row += grid[i][j]
    print(row)


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

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

  int a, b, k;
  cin >> a >> b >> k;

  set<int> s;
  for (int i = a; i <= min(b, a+k-1); ++i) s.emplace(i);
  for (int i = max(a+k, b-k+1); i <= b; ++i) s.emplace(i);

  for (auto e : s) cout << e << '\n';

  return (0);
}


Measured memory_bytes: 3656
#include <iostream>
#include <cctype>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <string>
#include <functional>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define pb push_back 
#define YES cout<<"YES"<<endl
#define Yes cout<<"Yes"<<endl
#define NO cout<<"NO"<<endl
#define No cout<<"No"<<endl
typedef long long ll;
const int INF = 100000000, mod = 1000000007;
const ll LLINF = 1LL << 50;
using namespace std;


int main() {
    int n;
    bool y = false;
    cin >> n;
    for (int i = 0; i < n; i++) {
        char t;
        cin >> t;
        if (t == 'Y')y = true;
    }
    if (y)cout << "Four" << endl;
    else cout << "Three" << endl;
    return 0;
}


Measured memory_bytes: 256
#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

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

template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
	for (const auto &e : vec) os << e << (&e == &vec.back() ? "" : " ");
	return os;
}

template <class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
	os << p.first << " " << p.second;
	return os;
}

template <class T1, class T2>
ostream &operator<<(ostream &os, const map<T1, T2> &mp) {
	for (const auto &e : mp) os << "[" << e << "] ";
	return os;
}

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

int main() {

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

	int H, W;
	cin >> H >> W;

	vector<string> grid(H);
	for (int i = 0; i < H; i++) cin >> grid[i];

	cout << string(W + 2, '#') << "\n"; 
	for (int i = 0; i < H; i++) {

		cout << '#';
		for (int j = 0; j < W; j++) cout << grid[i][j];
		cout << "#\n";

	}
	cout << string(W + 2, '#') << "\n";


	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>
#include <fstream>
#include <bitset>
#include <time.h>
#include <tuple>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef complex<double> Point;

#define PI acos(-1.0)
#define EPS 1e-10
const ll INF = (1LL << 60) - 1;
const ll MOD = 1e9 + 7;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,N) for(int i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )
#define fi first
#define se second
#define N_SIZE (1LL << 20)
#define NIL -1
#define MAX_N 100100 * 3

int n;
int q, k;

class DK {
public:
	struct edge {
		int to;
		ll cost;
	};

	int prev[100010];
	ll d[100010];
	vector<edge> G[100010];//各頂点からの辺

	void dijkstra(int start) {
		fill(d, d + 100010, INF);
		d[start] = 0;
		fill(prev, prev + 100010, -1);

		priority_queue<P, vector<P>, greater<P>> que;
		que.push(P(0, start));

		while (!que.empty()) {
			P p = que.top();
			que.pop();
			int v = p.second;
			if (d[v] < p.first)continue;
			for (int i = 0; i < G[v].size(); i++) {
				edge e = G[v][i];
				if (d[e.to] > d[v] + e.cost) {
					d[e.to] = d[v] + e.cost;
					prev[e.to] = v;
					que.push(P(d[e.to], e.to));
				}
			}
		}
	}

	vector<int> get_path(int goal) {
		vector<int> path;
		for (int t = goal; t != -1; t = prev[t]) {
			path.push_back(t);
		}//このままでは逆順なのでひっくり返す
		reverse(ALL(path));
		return path;
	}
};

DK dk;

int main() {
	cin >> n;
	rep(i, n - 1) {
		int a, b, c;
		cin >> a >> b >> c;
		dk.G[a].push_back({ b,c });
		dk.G[b].push_back({ a,c });
	}
	cin >> q >> k;
	dk.dijkstra(k);
	rep(i, q) {
		int x, y;
		cin >> x >> y;
		cout << dk.d[x] + dk.d[y] << endl;
	}
}

Measured memory_bytes: 11504
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
 
int K;

int main(void){
	
	scanf("%d", &K);
	
	if(K % 2 == 0) printf("%d\n", (K / 2) * (K / 2));
	else printf("%d\n", (K / 2) * (K / 2 + 1));
	
    return 0;
}

Measured memory_bytes: 256
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right #func(リスト,値)
from heapq import heapify, heappop, heappush
from math import *

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)

s = input()
t = []
for i in range(len(s)):
    if s[i]=='B':
        if len(t)>0:
            t = t[:len(t)-1]
    else:
        t.append(s[i])
print(''.join(t))

Measured memory_bytes: 65692
#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
using namespace std;
int main()
{
	string b;
	cin >> b;
	if (b == "A") {
		cout << "T";
	}
	if (b == "T") {
		cout << "A";
	}
	if (b == "G") {
		cout << "C";
	}
	if (b == "C") {
		cout << "G";
	}
	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Integer> valueList = new ArrayList<>();
        for (int i=0; i<n; i++){
            valueList.add(sc.nextInt());
        }
        List<Integer> costList = new ArrayList<>();
        for (int i=0; i<n; i++){
            costList.add(sc.nextInt());
        }

        int totalBenefit = 0;

        for (int i=0; i<n; i++){
            int benefit = valueList.get(i) - costList.get(i);
            if (benefit > 0){
                totalBenefit += benefit;
            }
        }

        System.out.println(totalBenefit);
    }
}

Measured memory_bytes: 22996
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;

int main(){
  int N,M;
  cin >> N >> M;
  vector<pair<ll,int>> p;
  for(int i=0;i<N;i++){
      int x,y;
      cin >> x >> y;
      p.emplace_back(x, y);
  }
  sort(p.begin(),p.end());


  ll ans=0;
  for(int i=0;i<N;i++){
    if(M>p[i].second){
      ans+=p[i].first*p[i].second;
      M=M-p[i].second;
    }
    else{
      for(int j=0;j<p[i].second;j++){
        ans+=p[i].first;
        M=M-1;
        if(M==0) break;
      }
    }
    if(M==0) break;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 2420
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll n,x;
	cin>>n>>x;
	ll a[n];
	for(ll i=0;i<n;i++)
		cin>>a[i];
	ll d=0;
	ll ans=1;
	for(ll i=0;i<n;i++)
	{
		d=d+a[i];
		if (d<=x)
			ans++;
	}
	cout<<ans;
}

Measured memory_bytes: 256
package main

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

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	sc.Split(bufio.ScanWords)
	var n [3]int
	for i := 0; i < 3; i++ {
		n[i] = nextInt()
	}
	var min int = 1000000
	for i := 0; i < 3; i++ {
		for j := 0; j < 3; j++ {
			if i != j {
				for k := 0; k < 3; k++ {
					if j != k && i != k {
						var cost = 0
						cost += int(math.Abs(float64(n[j] - n[i])))
						cost += int(math.Abs(float64(n[k] - n[j])))
						if min > cost {
							min = cost
						}
					}
				}
			}
		}
	}
	fmt.Print(min)
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define forn(i,n) for(int i = 0; i < (int) n; ++i)
#define ios ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

int go(int x) {
  int ans = 0;
  while(x != 0) {
    int pc = __builtin_popcount(x);
    x %= pc;
    ans++;
  }
  return ans;
}

int main() {
  ios;
  int n;
  string x;
  cin >> n >> x;

  int pc = 0;
  forn(i, n) pc += x[i] == '1';

  vector<int> p2m(n + 5), p2p(n + 5);
  p2m[0] = p2p[0] = 1;
  forn(i, p2m.size() - 1) {
    if (pc > 1) p2m[i + 1] = (2 * p2m[i]) % (pc - 1);
    p2p[i + 1] = (2 * p2p[i]) % (pc + 1);
  }

  int mm = 0, mp = 0;
  forn(i, n) {
    if (pc > 1) mm = (2 * mm + x[i] - '0') % (pc - 1);
    mp = (2 * mp + x[i] - '0') % (pc + 1);
  }

  forn(i, n) {
    int rpc = (x[i] == '1' ? pc - 1 : pc + 1);
    int real = (x[i] == '1' ? mm : mp);
    if (rpc == 0) {
      cout << "0\n";
      continue;
    }

    if (x[i] == '1') real -= p2m[n - i - 1];
    else real += p2p[n - i - 1];

    real = (real % rpc + rpc) % rpc;
    int ans = go(real);
    cout << ans + 1 << "\n";
  }
}


Measured memory_bytes: 5188
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define rep2(i,n) for(int i=0;i<=n;i++)
#define repr(i,a,n) for(int i=a;i<n;i++)
#define all(a) a.begin(),a.end()
#define P pair<long long,long long>
#define double long double
#define INF 1e10
#define MOD 1e9+7
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 Graph = vector<vector<int>>;
signed main(){
  int a,b;
  cin>>a>>b;
  if((a+b)%2==1)
    cout<<"IMPOSSIBLE";
  else
    cout<<(a+b)/2;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define rep(i,n) for(int (i) = 0, i_len = n; (i) < (i_len); ++(i))
#define repp(i,n) for(int (i) = 1, i_len = n; (i) <= (i_len); ++(i))
#define per(i,n) for(int (i) = n-1; (i) >= 0; --(i))
#define perr(i,n) for(int (i) = n; (i) > 0; --(i))
#define sz(x) ((int)(x).size())
#define popcnt __builtin_popcount
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).begin(),(v).end(),greater<>()
#define Pi 3.1415926535
#define MOD 1000000007;
using namespace std;
using ll = long long;
using pint = pair<int,int>;
using itn = int;
using vint = vector<int>;
template<class T,class S> inline bool chmax(T& a, S b){if(a<b){a = b; return true;} return false;}
template<class T,class S> inline bool chmin(T& a, S b){if(a>b){a = b; return true;} return false;}
template<class T> T gcd(T a, T b){return b?gcd(b,a%b):a;}
template<class T> T lcm(T a, T b){return a*b/gcd(a,b);}
void yes(){cout << "Yes" << endl;}
void no(){cout << "No" << endl;}

int solve(){
    int n; cin >> n;
    vector<string> s(n); rep(i,n) cin >> s[i];
    sort(all(s));
    int ans = n;
    rep(i,n-1){
        if(s[i] == s[i+1]) --ans;
    }

    cout << ans << endl;

    return 0;
}

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


Measured memory_bytes: 9536
from itertools import accumulate

n,k=map(int, input().split())
p=list(map(int, input().split()))

acc=list(accumulate(p))
ans=sum(p[:k])
for i in range(k,n):
    ans=max(ans, acc[i]-acc[i-k])
print(ans/2+0.5*k)


Measured memory_bytes: 25152
#include <bits/stdc++.h>
using namespace std;
#define REP(i, init, n) for(int i = (int)(init); i < (int)(n); i++)
long Abs(long a, long b){
    long res;
    if(a > b) res = a - b;
    else res = b - a;
    return res;
}

int main() {
    long N, K;
    cin>>N>>K;
    long res1 = N % K;
    long res2 = K - res1;
    cout << min(res1, res2) << endl;
    return 0;
}

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

using namespace std;
typedef long long ll;

void dfs(ll s, ll t,int depth, int ans){
  if(s==t){
    cout<<ans<<endl;
  }
  else{
    if(s%2)s++,ans++;
    if(t%2)t--,ans++;
    dfs(s/2, t/2, depth+1,ans);
  }
}

int main(){

  int N;
  cin>>N;
  while(N--){
    ll s,t;
    cin>>s>>t;
    s+=1LL<<32;
    t+=1LL<<32;
    dfs(s,t,0,0);
  }
  
  return 0;
}

Measured memory_bytes: 3068
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<n;i++)
#define loop(i,a,n) for(i=a;i<n;i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define first F
#define second S

typedef vector<int> vi;
typedef pair<int,int> pii;

int main(void) {
  int i,j,k;
  int n;
  cin>>n;
  vi v(n,0);
  vector<vi> score(n,vi(3));
  rep(i,n)
    cin>>score[i][0]>>score[i][1]>>score[i][2];
  rep(i,3)rep(j,n){
    v[j]+=score[j][i];
    rep(k,n)
      if(score[j][i]==score[k][i] && j!=k){
        v[j]-=score[j][i];
        break;
      }
  }
  rep(i,n)
    cout<<v[i]<<endl;
}

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

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repr(i, n) for(int i = (n-1); i >= 0; --i)

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

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

const int MAX = 200005;
const int INF = 1001001001;
const int MOD = 1000000007;

int main(){
    int K, A, B;
    cin >> K >> A >> B;

    bool ans = false;
    for (int i = A; i <= B; ++i) {
        if (i % K == 0) ans = true;
    }

    cout << (ans? "OK" : "NG") << endl;
}

Measured memory_bytes: 3640
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
/*
//#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
*/

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
/*
//#if __cplusplus >= 201103L
#include <array>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
*/
using namespace std;
#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl

#define uni(x) x.erase(unique(all(x)),x.end())
template<class T,class U>inline void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>inline void chmax(T &t,U f){if(t<f)t=f;}
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) > (b) ? (b) : (a))

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;

#define INF INT_MAX/3
#define MAX_N 1000
#define M_INF 1000000000
int n,m,v,i;
int a,b,c,d,e,f;
int A,B,C,D,E,F;
void solve(){
   cin.tie(0);
  ios::sync_with_stdio(false);
  cin>>A>>B>>C>>D>>E>>F;
  double bor = e/100,ans = -1,ans_t,ans_s;
  for(a=0;a*A*100<=F;a++){
    for(b=0;a*A*100+b*B*100<=F;b++){
      for(c=0;a*A*100+b*B*100+c<=F;c++){
        for(d=0;a*A*100+b*B*100+c*C+d*D<=F;d++){
          if(c*C+d*D > (a*A+b*B)*E) break;
          double tmp = (c*C+d*D) * (1.0)/(a*A*100+b*B*100+c*C+d*D);
          if(ans < tmp){
            ans = tmp;
            ans_t = (a*A*100+b*B*100+c*C+d*D);
            ans_s = (c*C+d*D);
          }
        }
      }
    }
  }

  cout<<ans_t<<" "<<ans_s<<endl;
  
}

int main(){
  solve();
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef priority_queue<int> PQ;
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));
//priority_queue<int,vector<int>, greater<int> > q2;



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

	int N, K;
	cin >> N >> K;
	VI V(N);
	REP(i, N) 
		cin >> V[i];

	int M = min(N, K);
	int ans = 0;
	for (int a = 0; a <= M; a++) {
		for (int b = 0; b <= M - a; b++) {
			int cnt = 0;
			PQ Q;
			REP(i, a) {
				cnt += V[i];
				if (V[i] < 0) {
					Q.push(V[i] * -1);
				}
			}
			REP(i, b) {
				cnt += V[N - 1 - i];
				if (V[N - 1 - i] < 0) {
					Q.push(V[N - 1 - i] * -1);
				}
			}
			int k = K - a - b;
			while (!Q.empty() && k > 0) {
				k--;
				cnt += Q.top();
				Q.pop();
			}
			ans = max(ans, cnt);
		}
	}

	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 256
s=list(input())
for i in range(len(s)):
  if i%2==1:
    if s[i]=='L' or s[i]=='U' or s[i]=='D':
      pass
    else:
      print('No')
      exit()
  else:
    if s[i]=='R' or s[i]=='U' or s[i]=='D':
      pass
    else:
      print('No')
      exit()
    
print('Yes')    
    

    

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

int main(){
  int N;
  string S;
  cin >> N;
  cin >> S;
  int ans = 0;
  for(int i = 1; i < S.size(); i++){
    bool r[30], l[30];
    fill(r, r+30, false),   fill(l, l+30, false);
    for(int j = 0; j < i; j++) l[S[j] - 'a'] = true;
    for(int j = S.size() -1; j >= i; j--) r[S[j] - 'a'] = true;
    int a = 0;
    for(int i = 0; i < 30; i++){
      if(r[i] && l[i]) a++;
    }
    ans = max(ans, a);
  }
  cout << ans << endl;
  return 0;
}


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

#ifdef DEBUG
#include "../include/debug.hpp"
#else
#define debug(...) 42
#endif

const string ini = "SWWSS";
int N;
string s;

char trans(char animal, char saying) {
    if (animal == 'S') return saying;
    return saying == 'o' ? 'x' : 'o';
}

string solve(string t) {
    for (int i=0; i<N-2; ++i) {
        if (trans(t[i], s[i]) == 'o') {
            t[i+1] = t[(i-1+N)%N];
        } else {
            t[i+1] = (t[(i-1+N)%N] == 'S' ? 'W' : 'S');
        }
    }
    for (int i=N-2; i<=N-1; ++i) {
        if (trans(t[i], s[i]) == 'o' && t[(i-1+N)%N] != t[(i+1+N)%N]) return "";
        if (trans(t[i], s[i]) == 'x' && t[(i-1+N)%N] == t[(i+1+N)%N]) return "";
    }
    return t;
}

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

    cin >> N >> s;

    string t = "";
    for (int i=0; i<N-2; ++i) t += ".";

    for (int i=0; i<4; ++i) {
        string res = solve(ini[i]+t+ini[i+1]);
        if (res != "") {
            cout << res << endl;
            return 0;
        }
    }
    cout << -1 << endl;

    return 0;
}

Measured memory_bytes: 768
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from heapq import heapify, heappop, heappush
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
H = [INT() for i in range(N)]
H.sort()
ans = INF
for i in range(N-K+1):
    mi = H[i]
    ma = H[i+K-1]
    tmp = ma - mi
    ans = min(tmp, ans)
print(ans)


Measured memory_bytes: 8132
#pragma GCC optimize(2)
#pragma GCC optimize(3)   
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector < ll > vl;
typedef vector < vl > vvl;
typedef pair < ll, ll > pll;
typedef vector < pair < ll, ll > > vpll;
#define kill freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define pb push_back
#define fo(i,n) for(ll i=0;i<n;i++)
#define rev(i,n) for(ll i=n-1;i>=0;i--)
#define all(c) c.begin(), c.end()
#define go(c,it) for(auto it=(c).begin(); it!=(c).end(); it++)
#define fi first
#define se second
#define MOD 998244353
#define Boost() ios_base::sync_with_stdio(false);cin.tie(NULL)
#define MOD1 1000000007
ll power(ll a, ll b){ll res=1;while(b>0){if(b&1){res=(res*a)%MOD;}a=(a*a)%MOD;b>>=1LL;}return res;}
ll fermat_inv(ll y){return power(y,MOD-2);}
ll gcd(ll a, ll b){return (b==0)?a:gcd(b,a%b);}
#define oo LLONG_MAX
const ll dx[]={-1,0,1, 0,-1,1, 1,-1};
const ll dy[]={ 0,1,0,-1, 1,1,-1,-1};

void solve(){
  ll n,k;
  cin>>n>>k;
  vl l(k),r(k);
  fo(i,k){
     cin>>l[i]>>r[i];
  }
  ll ans = 0;
  ll dp[n+1] = {0};
  dp[1] = 1;
  dp[2] = -1;
  for(ll i = 1;i<=n;i++){
      dp[i] = (dp[i]+dp[i-1])%MOD;
      fo(j,k){
          ll left = l[j];
          ll right = r[j]+1;
          if(i+left<=n)
            dp[i+left] = (dp[i+left]+dp[i])%MOD;
          if(i+right<=n)
            dp[i+right] = (dp[i+right]-dp[i]+MOD)%MOD;
      }
  }
  cout<<dp[n];
}

int main(){
    Boost();
    ll T = 1;
    //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 5172
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

int main(){
    int A, B, C, K;
    cin >> A >> B >> C >> K;
    vector<int> integer(3);
    integer[0] = A;
    integer[1] = B;
    integer[2] = C;
    
    for(int i = 0; i < K; i++){
        sort(integer.begin(), integer.end(), greater<int>());
        integer[0] *= 2;
    }
    
    cout << accumulate(integer.begin(), integer.end(), 0) << endl;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**7)
N, Q = map(int, input().split())
edges = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)
Query = [0]*N
for _ in range(Q):
    p, x = map(int, input().split())
    Query[p-1] += x
ans = [0]*N
past = [0]*N
def dfs(start,point):
    past[start] = 1
    point = point + Query[start]
    ans[start] = point
    for target in edges[start]:
        if past[target] == 0:
            dfs(target,point)
dfs(0,0)
print(*ans)

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

#define int ll
#define FOR(i,n,k) for(int i=n;i<k;i++)
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

int32_t main()
{
    IOS;
    int r,w;
    cin>>r>>w;
    string s[r];
    FOR(i,0,r) cin>>s[i];
    FOR(i,0,r) cout<<s[i]<<"\n"<<s[i]<<"\n";
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define M 1000000007
#define N 55
using namespace std;
typedef long long ll;
string num[3];
ll d[N][2],ans;

string get_num(int x,int y){
  string res;
  if(num[y][x]!='?')res+=num[y][x];
  else res+="0123456789";
  return res;
}

void update(int x){
  string a=get_num(x,0);
  string b=get_num(x,1);
  string c=get_num(x,2);

  ll A=0,B=0,C=0,D=0;
  for(int i=0;i<a.size();i++){
    for(int j=0;j<b.size();j++){
      for(int k=0;k<c.size();k++){
	int sum=a[i]-'0'+b[j]-'0';
	int Ans=c[k]-'0';
	if(!x&&(a[i]=='0'||b[j]=='0'||c[k]=='0'))continue;
	if(sum%10==Ans){
	  if(sum<10)A++;
	  else B++;
	}
	if((sum+1)%10==Ans){
	  if(sum+1<10)C++;
	  else D++;
	}
      }
    }
  }
  
  if(!x)ans=(d[x][0]*A+d[x][1]*C)%M;
  else{
    d[x-1][0]=(d[x][0]*A+d[x][1]*C)%M;
    d[x-1][1]=(d[x][0]*B+d[x][1]*D)%M;
  }
}

int main(){
  while(1){
    cin>>num[0];
    if(num[0]=="0")break;
    cin>>num[1]>>num[2];

    memset(d,0,sizeof(d));
    d[num[0].size()-1][0]=1;
    
    for(int i=num[0].size()-1;i>=0;i--)update(i);
    
    cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 3132
N=int(input())
n=len(str(N))
m=(n//2)
def wari(x):
    array=[]
    if m==0:
        for j in range(9,0,-1):
            if N%j==0:
                c=max(len(str(N//j)),len(str(j)))
                array.append(c)
                break
        
    for i in range(m+1):
        if i==0:
            for j in range(9,0,-1):
                if N%j==0:
                    c=max(len(str(N//j)),len(str(j)))
                    array.append(c)
                    break
        else:
            for j in range((10**(i+1))-1,(10**i)-1,-1):
                if N%j==0:
                    c=max(len(str(N//j)),len(str(j)))
                    array.append(c)
                    break
    return min(array)
print(wari(N))

Measured memory_bytes: 3064
import std.stdio, std.conv, std.string, std.bigint;
import std.math, std.random, std.datetime;
import std.array, std.range, std.algorithm, std.container;
string read(){ static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res; }

void main(){
	
	long a = read.to!long;
	long b = read.to!long;
	long c = read.to!long;
	
	long k = read.to!long;
	
	long ans;
	if(k % 2) ans = b - a;
	else ans = a - b;
	
	if(ans > 1_000_000_000_000_000_000) writeln("Unfair");
	else ans.writeln;
	
	}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
int main () {
  int n,l;
  cin >>n>>l;
  vector<int>a(n);
  for (int i=0;i<n;i++){
    a.at(i) = l+i;
  }

  int taste =0;
  for(int i=0;i<n;i++){
    taste +=a.at(i);
  }

  int ans = 100100101;
  for(int i=0;i<n;i++){
    int eattaste = taste - a.at(i);
    if(abs(eattaste -taste) < abs(ans -taste))ans =eattaste;
  }
  cout <<ans<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
#define ll long long int
#define tc int t; cin>>t; while(t--)
#define inn ll arr[n]; for(int i=0;i<n;i++) cin>>arr[i];
#define fora(i,n); for(ll i=0;i<n;i++)
#define forb(i,a,n); for(int i=a;i<n;i++)
#define mod 1000000007

int main()
{

//THIS CODE IS CREATED BY ANSHJAIN18

ll n;
cin>>n;
map<pair<ll,ll>,ll> mp;
for(ll i=1;i<=n;i++)
{

    ll num=i;
    string s=to_string(num);
    mp[{s[0]-'0',s.back()-'0'}]++;

}
ll cnt=0;
for(auto it:mp)
{
    ll a=it.first.first;
    ll b=it.first.second;
    if(mp.find(make_pair(b,a))!=mp.end())
    {   ll s=(mp[{b,a}]%mod*it.second%mod)%mod;
        cnt=(cnt+s)%mod;
    }


}
cout<<cnt;


return 0; }

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long n,a,b,i,sum=0,c;
	cin>>n>>a>>b;
    c=n/(a+b);
    sum=a*c+sum;
    c=n%(a+b);
    if(c<=a)
    sum=sum+c;
    else
    sum=sum+a;
	cout<<sum<<endl;
	return 0;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n, k = map(int, input().split())
x = list( map(int, input().split()))

ans = float('inf')
for i in range(n-k+1):
    left = x[i]
    right = x[i+k-1]
    if left <= 0 <= right:
        tmp = -(left) + right
        tmp += min(-left,right)
        ans = min(ans,tmp)
    elif 0 < left:
        ans = min(ans,right)
    elif right < 0:
        ans = min(ans,abs(left))

print(ans)

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

int A, B, C;

int f(int x, int y, int z) {
    if(x % 2 == 1 || y % 2 == 1 || z % 2 == 1) return 0;
    x /= 2, y /= 2, z /= 2;
    return f(y + z, x + z, x + y) + 1;
}

int main() {
    scanf("%d %d %d", &A, &B, &C);
    if(A % 2 || B % 2 || C % 2) return puts("0"),0;
    if(A == B && B == C) return puts("-1"),0;
    printf("%d\n", f(A, B, C));
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,n,m) for(int i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define REPR(i,n) for(int i=(n);i>=0;i--)
#define all(vec) vec.begin(),vec.end()
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<ll,ll>;
using PP=pair<ll,P>;
using vp=vector<P>;
using vpp=vector<PP>;
using vs=vector<string>;
#define fi first
#define se second
#define pb push_back
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
const ll MOD=1000000007LL;
const int INF=1<<30;
const ll LINF=1LL<<60;
int main(){
    int n;
    cin>>n;
    vi vec(n);
    REP(i,n){
        cin>>vec[i];
    }
    int ans=0;
    while(1){
        bool f=false;
        REP(i,n){
            if(!vec[i]){
                continue;
            }
            int r=i;
            while(r<n&&vec[r]){
                r++;
            }
            FOR(j,i,r){
                vec[j]--;
            }
            ans++;
            f=true;
            i=r;
        }
        if(!f){
            break;
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256