akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0;i<(n);i++)

int main(){
    int n;
    cin >> n;
    vector<int> h(n);

    rep(i, n){
        cin >> h.at(i);
    }
    string ans = "Yes";
    for(int i=n-1;i>0;i--){
        if(h.at(i-1) - h.at(i) == 1){
            h.at(i-1)-=1;
        }
        if(h.at(i) < h.at(i-1)){
            // cout << i << endl;
            ans="No";
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	static long n;

	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		// n = Long.parseLong(br.readLine());

		String str[] = br.readLine().split(" ");

		int N = Integer.parseInt(str[0]);
		int W = Integer.parseInt(str[1]);

		int n[] = new int[N];
		int weight[] = new int[N];

		for (int i = 0; i < N; i++) {
			str = br.readLine().split(" ");
			n[i] = Integer.parseInt(str[0]);
			weight[i] = Integer.parseInt(str[1]);
		}

		int dp[][] = new int[110][10010];

		for (int i = 0; i < N; i++) {
			for (int w = 0; w <= W; ++w) {
				if (weight[i] <= w) {
					dp[i + 1][w] = Math.max(dp[i][w], dp[i][w - weight[i]] + n[i]);
				} else {
					dp[i + 1][w] = dp[i][w];
				}
			}
		}
		System.out.println(dp[N][W]);
	}
}



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

int main() {
    int N; cin >> N;

    while(true) {
        if(to_string(N)[0] == to_string(N)[1] && to_string(N)[1] == to_string(N)[2]) {
            cout << N << endl;
            break;
        } else {
            N++;
        }
    }
}

Measured memory_bytes: 256
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt
from functools import lru_cache, reduce
INF = 1 << 60
mod = 1000000007
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# ここから書き始める
n, x = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
for i in range(1, n):
    if a[i - 1] + a[i] <= x:
        # print("a =", a, "ans =", ans)
        continue
    ans += a[i] + a[i - 1] - x
    # if a[i] > x:
    #     a[i] -= a[i] + a[i - 1] - x
    #     a[i] = max(a[i], 0)
    # elif a[i] + a[i - 1] > x:
    #     a[i] = 0
    a[i] = max(x - a[i - 1], 0)
    # print("a =", a, "ans =", ans)
print(ans)


Measured memory_bytes: 16248
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
typedef pair<int, int> pii;
/* constant */
const int INF = 1 << 30;
const ll LINF = 1LL << 61;
const int NIL = -1;
const int MAX = 10000;
const int MOD = 1000000007;
const double pi = 3.141592653589;
/* global variables */
/* function */
/* main */
int main(){
    int n;
    ll k;
    cin >> n >> k;
    vector<int> nextTown(n + 1);
    for (int i = 1; i <= n; i++) cin >> nextTown[i];

    vector<int> visited(n + 5, NIL), town(n + 5, 0);
    ll loopSize = 0, beforeLoop = 0;
    int t = 1;  // start: town-1
    visited[t] = 0;
    town[0] = t;
    for (int cnt = 1; cnt <= n; cnt++) {
        t = nextTown[t]; // 移動
        if (visited[t] != NIL) {
            loopSize = cnt - visited[t];
            beforeLoop = visited[t];
            break;
        }
        town[cnt] = t;
        visited[t] = cnt;
    }
    if (k <= beforeLoop) {
        cout << town[k] << '\n';
    }
    else {
        ll loopRest = (k - beforeLoop) % loopSize;
        cout << town[beforeLoop + loopRest] << '\n';
    }
}


Measured memory_bytes: 5608
import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int[] dice = new int[6];
        for(int i = 0;i < 6;i++){
            dice[i] = sc.nextInt();
        }
        
        int tmp;
        String str = sc.next();
        
        for(int i = 0;i < str.length();i++){
            char order = str.charAt(i);
            switch(order){
                case 'S':
                    tmp = dice[0];
                    dice[0] = dice[4];
                    dice[4] = dice[5];
                    dice[5] = dice[1];
                    dice[1] = tmp;
                    break;
                case 'N':
                    tmp = dice[0];
                    dice[0] = dice[1];
                    dice[1] = dice[5];
                    dice[5] = dice[4];
                    dice[4] = tmp;
                    break;
                case 'W':
                    tmp = dice[0];
                    dice[0] = dice[2];
                    dice[2] = dice[5];
                    dice[5] = dice[3];
                    dice[3] = tmp;
                    break;
                case 'E':
                    tmp = dice[0];
                    dice[0] = dice[3];
                    dice[3] = dice[5];
                    dice[5] = dice[2];
                    dice[2] = tmp;
                    break;
            }
        }
        System.out.println(dice[0]);
    }
}


Measured memory_bytes: 26308
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }

/*
 <url:http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2155>
 問題文============================================================
 =================================================================
 解説=============================================================
 ================================================================
 */
int N,M;
ll solve(){
    ll res = 0;
    using Items = tuple<int,int,int>;
    vector<Items> com(M);
    for(int i = 0; i < M;i++){
        int t,s,d; cin >> t >> s >> d;
        com[i] = Items(t,s,d);
    }
    sort(com.begin(),com.end());
    vector<int> infected(N+1,0); infected[1] = true;
    for(int i = 0; i < M;i++){
        infected[get<2>(com[i])] |= infected[get<1>(com[i])];
    }
    res = accumulate(infected.begin(),infected.end(),0LL);
    return res;
}
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    while(cin >> N >> M,N|M){
        cout << solve() << endl;
    }
    return 0;
}



Measured memory_bytes: 3456
#include <iostream>
#include <queue>

using namespace std;

int main()
{
	for(int n,l;cin>>n>>l && n|l;){
		vector<int> ices(n);
		for(int i=0;i<n;i++)
			cin>>ices[i];
		
		priority_queue<pair<int,int> > pq;
		for(int i=0;i<n;i++)
			pq.push(make_pair(ices[i],i));
		
		vector<int> bs(n);
		int t=0;
		while(pq.size()){
			int i=pq.top().second;
			pq.pop();
			bs[i]=l-ices[i]+max(i>0?bs[i-1]:0,i<n-1?bs[i+1]:0);
			t=max(t,bs[i]);
		}
		cout<<t<<endl;
	}
	
	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <numeric>

using namespace std;
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define reppe(i,a,b) for(int i = (int)(a) ; i <= (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)
#define repme(i,a,b) for(int i = (int)(a) ; i >= (int)(b) ; --i)

typedef long long ll;

long long GCD(long long a, long long b){if(b==0)return a;return GCD(b,a%b);}

int main() {
    int N; cin >> N;
    vector<int> P(N);
    repp(i,0,N) cin >> P[i];
    int res = 1;
    int minN = P[0];
    repp(i,1,N) {
        if (minN > P[i]) res++;
        minN = min(minN, P[i]);
    }
    cout << res << endl;
}


Measured memory_bytes: 1024
import queue
n = int(input())
tree_node = [set() for _ in range(n)]
hen = []
hen_col = {}
for i in range(n-1):
    a,b = map(int,input().split())
    tree_node[a-1].add(b)
    hen.append([a,b])
    hen_col[str(a)+'-'+str(b)] = 0
q = queue.Queue()
q.put(1)
parent_node = [0] * n
parent_color = [0] * n
maxcol = 0
while not q.empty():
    col = 0
    nod = q.get()
    for i,c in enumerate(tree_node[nod-1]):
        if i+1 == parent_color[nod-1]:col+=1
        tempcol = i+1+col
        parent_color[c-1]=tempcol
        maxcol = max(maxcol,tempcol)
        q.put(c)
        l = min(nod,c)
        r = max(nod,c)
        hen_col[str(l)+'-'+str(r)] = tempcol
        parent_node[c-1] = nod

print(maxcol)
for t in hen:
    tempstr = str(t[0])+'-'+str(t[1])
    print(hen_col[tempstr])

Measured memory_bytes: 59204
import sys

A=[list(map(int,input().split())) for i in range(3)]
N=int(input())
b=[]
for i in range(N):
    b.append(int(input()))


for i in range(3):
    for j in range(3):
        for x in range(N):
            if A[i][j]==b[x]:
                A[i][j]=0

for i in range(3):
    if A[i][0]==0 and A[i][1]==0 and A[i][2]==0:
        print("Yes")
        sys.exit(0)
for i in range(3):
    if A[0][i]==0 and A[1][i]==0 and A[2][i]==0:
        print("Yes")
        sys.exit(0)
if A[0][0] == 0 and A[1][1] == 0 and A[2][2] == 0:
    print("Yes")
    sys.exit(0)
if A[0][2] == 0 and A[1][1] == 0 and A[2][0] == 0:
    print("Yes")
    sys.exit(0)
print("No")

Measured memory_bytes: 3064
#include <stdio.h>
int main(void)
{
    int a;
    int b;
    int c;
    scanf("%d",&a);
    scanf("%d",&b);

    if(a == 1 || b == 1)
    {
        if(a == 2 || b == 2)
        {
            c = 3;
        }
        else
        {
            c = 2;
        }
        
    }
    else
    {
        c = 1;
    }
    
    printf("%d",c);
}

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

#define zton(i,n) for(int i=0;i<=n;i++)
#define oneton(i,n) for(int i=1;i<=n;i++)
#define fo(i,n) for(int i=0;i<n;i++)
#define fab(i,a,b) for(int i=a;i<b;i++)
#define loop(i,b,a) for(int i=a;i>=b;i--)
#define dsort(arr,n) sort(arr, arr + n, greater<int>())
#define vsortd(a) sort(a.begin(), a.end(), greater<double>())
#define vsort(a) sort(a.begin(), a.end())
#define ll long long int
#define test int tc;cin>>tc;while(tc--)
#define dbg(x) cout<<#x<<'='<<(x)<<endl;
#define dbg2(x,y) cout<<#x<<'='<<(x)<<endl<<#y<<'='<<(y)<<endl;
#define dbg3(x,y,z) cout<<#x<<'='<<(x)<<endl<<#y<<'='<<(y)<<endl<<#z<<"="<<(z)<<endl;
#define dbg4(x,y,z,w) cout<<#x<<'='<<(x)<<endl<<#y<<'='<<(y)<<endl<<#z<<"="<<(z)<<endl<<#w<<"="<<(w)<<endl;
#define minheap priority_queue <int, vector<int>, greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define pb push_back
#define ff first
#define ss second
#define mpr make_pair
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define mkv vector<int>
#define allzero(dp) memset(dp,0,sizeof(dp))
#define endl "\n"
#define print(x) cout<<x<<endl;

const int mod=1e9+7;
using namespace std;
bool sortcol( const vector<int>& v1,const vector<int>& v2 ) {return v1[1] < v2[1];}

void fastio()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
}

bool compare(const pair<ll,ll> &a,const pair<ll,ll> &b){
    if(a.first>b.first)return true;
    if(a.first==b.first)return a.second<b.second;
    return false;
}

ll power(ll x, ll y){
    ll res = 1;x=x%mod;
    while(y>0){
        if(y&1)res=(res*x)%mod;
        y=y>>1;x=(x*x)%mod;}
    return res;
}

vector<int>ch;
void solve()
{
    int n;cin>>n;
    int a[n];
    fo(i,n){
        cin>>a[i];
    }
    sort(a,a+n);
    int ans=0;
    fo(i,n){
        fo(j,n){
            fo(k,n){
                if(a[k]>a[j]&&a[j]>a[i]){
                //    dbg3(a[i],a[j],a[k])
                    if(a[i]+a[j]>a[k]&&a[j]+a[k]>a[i]&&a[k]+a[i]>a[j]){
                        ans++;
                    }
                }
            }
        }
    }
    print(ans)
}

int main()
{
  //  fastio();
   // test
    solve();
}


Measured memory_bytes: 3636
#!/usr/bin/python3

from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

def main():
    S = input()
    print(700 + S.count("o") * 100)


if __name__ == '__main__':
    main()


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

int main() {
    int n; cin >> n;
    int a[100];
    rep(i,n) cin >> a[i];
    int ans=0;
    rep(i,n) {
        if ((i+1)%2 == 1 and a[i]%2==1) ans ++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3620
import sys


def dfs(A: list):
    if len(A) == n:
        for i in range(len(A)-1):
            if A[i+1] not in node[A[i]]:
                break
            if i == n-2:
                ans[0] += 1
        return
    for v in range(2, n+1):
        if v not in A:
            A.append(v)
            dfs(A)
            A.pop()


n, m = map(int, input().split())
node = [set() for _ in range(n+1)]
for x in sys.stdin.readlines():
    a, b = map(int, x.split())
    node[a].add(b)
    node[b].add(a)
ans = [0]
dfs([1])
print(ans[0])


Measured memory_bytes: 9128
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,tune=native")
//Use above if bruteforcing with lots of small operations. Or just use it anytime, there's no downside.
//AVX is better slightly
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef long double ld;

#define rc(s) return cout << s, 0
#define fi first
#define se second
#define L (nod << 1)
#define R (L | 1)
#define smax(X, Y) ((X) > (Y) ? (X) : (Y))
#define smin(X, Y) ((X) < (Y) ? (X) : (Y))

const ll inf = (1LL<<62);
const int iinf = (1<<30);
//CLOCKS_PER_SEC

const int N = 200100;
int n, a[N], fw[N], ans[N], lvl[N];
vector <int> v[N];
vector <vector <int> > vec;
pii b[N];
stack <int> st;

void update(int idx, int val){
    for (; idx <= n; idx += (idx & -idx))
        fw[idx] += val;
}

int get(int idx){
    int rs = 0;
    for (; idx; idx -= (idx & -idx))
        rs += fw[idx];
    return rs;
}

void dfs(int q, int pr = -1){
    //cout << q << '\n';
    int st = 0, dr = vec.size() - 1;
    while (st <= dr){
        int mid = (st + dr) >> 1;
        if (vec[mid].back() < a[q]) st = mid + 1;
        else dr = mid - 1;
    }
    if (st >= vec.size()){
        vec.push_back(vector <int>());
    }
    vec[st].push_back(a[q]);
    ans[q] = vec.size();
    for (int it: v[q]){
        if (it == pr) continue;
        dfs(it, q);
    }
    vec[st].pop_back();
    if (vec.back().size() == 0) vec.pop_back();
}

int main(){
    //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    //ios_base::sync_with_stdio(0); cin.tie(0);
    //ifstream cin ("test.in");
    cin >> n;
    for (int i=1; i<=n; i++) cin >> a[i];
    for (int i=1; i<n; i++){
        int x, y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1);
    for (int i=1; i<=n; i++)
        cout << ans[i] << '\n';
    return 0;
}


Measured memory_bytes: 31508
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
const double PI = acos(-1);
const double EPS = 1e-9;
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; }



signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N; cin >> N;
	vector<vector<int>>A(N, vector<int>(N, INF));
	vector<vector<int>>B(A);
	rep(i, 0, N)rep(j, 0, N) { cin >> A[i][j]; }
	int n = N;
	//	M = vector<vector<pair<int, int>>>(n, vector<pair<int, int>>());


	rep(i, 0, N)rep(j, 0, N)rep(k, 0, N) {
		if (A[i][j] + A[j][k] == A[i][k]) {
			//dump(i, j, k);
			//dump(A[i][j], A[j][k], A[i][k]);
			//M[i].emplace_back(make_pair(j, A[i][j]));
			//M[j].emplace_back(make_pair(i, A[i][j]));
			//M[j].emplace_back(make_pair(k, A[j][k]));
			//M[k].emplace_back(make_pair(j, A[j][k]));
			chmin(B[i][j], A[i][j]);
			chmin(B[j][i], A[j][i]);
			chmin(B[j][k], A[j][k]);
			chmin(B[k][j], A[k][j]);

		}
	}
	rep(k, 0, n) {
		rep(i, 0, n) {
			if (B[i][k] == INF)continue;
			rep(j, 0, n) {
				if (B[k][j] == INF)continue;
				B[i][j] = min(B[i][j], B[i][k] + B[k][j]);
			}
		}
	}

	if (A != B)cout << -1 << endl;
	else {
		rep(i, 0, N)rep(j, 0, N)rep(k, 0, N) {
			if (i == j || j == k || i == k)continue;
			if (A[i][j] + A[j][k] == A[i][k]) {
				B[i][k] = B[k][i] = 0;
			}
		}

		int sum(0);
		rep(i, 0, N)rep(j, i, N)sum += B[i][j];
		dump(B);
		cout << sum << endl;
	}
	return 0;
}

Measured memory_bytes: 1664
/*<----------------------------------------------------------------------->

<-------------------------------------------------------------------------->
            _           __                _      _____ _____ _____ 
  ___ _   _| |__   ___ / _|_ __ ___  __ _| | __ |___  |___  |___  |
 / __| | | | '_ \ / _ \ |_| '__/ _ \/ _` | |/ /    / /   / /   / / 
| (__| |_| | |_) |  __/  _| | |  __/ (_| |   <    / /   / /   / /  
 \___|\__,_|_.__/ \___|_| |_|  \___|\__,_|_|\_\  /_/   /_/   /_/   

*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<ll> vi;
typedef vector<pll> vpll;
typedef unordered_map <ll,ll> umap ; 
//#pragma GCC optimize "trapv"
#define loop(i,a,b) for(ll i=a ;i<b;i++)
#define For(i,n) for(int i=0;i<(ll)n;i++)
#define Rev(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,n) for(int i=1;i<=n;++i)
#define F first
#define S second
#define pb push_back
#define em emplace_back
#define all(v) (v).begin(),(v).end()
#define mems(x, y) memset(x, y, sizeof(x))
#define sz(v) (v).size()
#define mp(a,b) make_pair(a,b)
#define pf(n) cout<<n<<"\n"
#define pff(n) cout << n << " " ; 
long const M=1e9+7;
const long mxN =1e5+2 ;
const long mxNN =1e6+2 ;
void solve(){
    int x,ans =0 ; cin >>  x;
    int rem = x -(x/500)*500 ;
    ans+=(x/500)*1000 ;
    rem= (rem/5)*5 ;
    ans+=rem ;
    pf(ans);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve() ;
    //ll t ; cin >> t ; while(t--)solve();
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int N = 500 + 10;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string s, t;
    cin >> s >> t;
    int n = s.size(), m = t.size(), ans = m;
    for (int i = 0; i <= n - m; ++i)
    {
        int cur = 0;
        for (int j = 0; j < m; ++j)
            cur += (s[i + j] != t[j]);
        ans = min(ans, cur);
    }
    cout << ans;
}

Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector< vector<int> > VII;
typedef pair<int,int> P;
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a) (a).begin(),(a).end()

int main(){
  int N;
  string S;
  cin>>N;
  cin>>S;
  int ans=0,X;
  rep(i,N){
    if(i){
      X=0;
      rep(j,N-i){
        if(S[j]==S[j+i]){
          X++;
          ans=max(ans,min(i,X));
        }else X=0;
      }
    }
  }
  cout<<ans<<endl;
}



Measured memory_bytes: 256
K,N = map(int,input().split())
L = list(map(int,input().split()))

L = [0] + L + [K]

# print(L)

max_distance = 0

for i in range(1,N):
    max_distance = max(max_distance,L[i+1]-L[i])

max_distance = max(max_distance,(L[-1]-L[-2])+(L[1]-L[0]))

print(K - max_distance)

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

char str[16];
int cnt[10], ans;

bool dfs(int pos, bool tt){
    if(pos >= 10) return true;
    if(cnt[pos] < 0) return false;
    if(cnt[pos] == 0) return dfs(pos+1, tt);
    bool ret;
    if(cnt[pos] == 1){
        if(pos > 7) return false;
        --cnt[pos+1]; --cnt[pos+2];
        ret = dfs(pos+1, tt);
        ++cnt[pos+1]; ++cnt[pos+2];
        return ret;
    }
    if(cnt[pos] == 2){
        if(!tt && dfs(pos+1, true)) return true;
        if(pos > 7) return false;
        cnt[pos+1] -= 2; cnt[pos+2] -= 2;
        ret = dfs(pos+1, tt);
        cnt[pos+1] += 2; cnt[pos+2] += 2;
        return ret;
    }
    if(cnt[pos] == 3){
        if(dfs(pos+1, tt)) return true;
        if(pos > 7) return false;
        --cnt[pos+1]; --cnt[pos+2];
        ret = dfs(pos+1, true);
        ++cnt[pos+1]; ++cnt[pos+2];
        return ret;
    }
    if(cnt[pos] == 4){
        if(pos > 7) return false;
        --cnt[pos+1]; --cnt[pos+2];
        ret = dfs(pos+1, tt);
        ++cnt[pos+1]; ++cnt[pos+2];
        if(ret) return true;
        cnt[pos+1] -= 2; cnt[pos+2] -= 2;
        ret = dfs(pos+1, true);
        cnt[pos+1] += 2; cnt[pos+2] += 2;
        return ret;
    }
}

int main(){
    while(scanf("%s", str) != EOF){
        fill(cnt, cnt+10, 0);
        for(char* it = str; *it; it++) ++cnt[*it-'0'];
        int c = 0;
        for(int x = 1; x <= 9; ++x){
            if(cnt[x] >= 4) continue;
            ++cnt[x];
            if( dfs(1, false) ){
                if(c) printf(" ");
                printf("%d", x);
                c++;
            }
            --cnt[x];
        }
        if(!c) printf("0");
        printf("\n");
    }
    return 0;
}

Measured memory_bytes: 1140
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <set>
#include <map>
#include <cassert>
#include <cstdio>
#include <cstdlib>

using namespace std;

typedef unsigned long long int ull;

int main(int argc,char** argv) {
	ull n,a;
	map<ull,int> c;
	cin >> n;
	for(ull i = 0;i < n;i++) {
		cin >> a;
		c[a]++;
	}
	multiset<ull> l;
	for(auto e:c) {
		if(e.second >= 2) l.insert(e.first);
		if(e.second >= 4) l.insert(e.first);
	}
	if(l.size() < 2){
		cout << 0;
		return 0;
	}
	auto itr = l.rbegin();
	ull res = *itr;
	itr++;
	res = res * *itr;
	cout << res << endl;
}


Measured memory_bytes: 6528
import sys
from datetime import *
from time import *

day = [ 'Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday', 'Sunday' ]

while True:
    try:
        user_input_date = '2004/'+'/'.join(input().split())
        if user_input_date == '2004/0/0':
            break
        else:
            a = datetime.strptime(user_input_date,'%Y/%m/%d')
            print(day[a.weekday()])
    except ValueError:
        pass
else:
    sys.exit(1)

Measured memory_bytes: 9048
object Main {

  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)

    val N = sc.nextInt()
    val A = Array.fill(N)(sc.nextInt()).sorted
    val B = Array.fill(N)(sc.nextInt())
    val C = Array.fill(N)(sc.nextInt()).sorted(Ordering.Int.reverse)

    // 3カテゴリーのパーツがそれぞれN個ずつあります
    // パーツのサイズ
    // 中部のパーツのサイズは、上部のパーツのサイズより真に大きく
    // 下部のパーツのサイズは、中部のパーツのサイズより真に大きくなければなりません
    // 作れる祭壇は何種類あるでしょうか/
    // ただし 2つの祭壇が異なるとは, 上部, 中部, 下部に使われるピースのうち少なくとも1つが異なる
    // 1つ決めた時の, そのパーツより大きいパーツはO(log N)で出すことができる
    // 普通にやると, O(N^2logN)とかになる, 間に合わない
    // なので, 中部を先に決めておく
    // 中部を決めた時, その時上部のパーツに使えるのは, 中部より小さいもの
    // 下部のパーツに使えるのは, 中部より大きいもの,
    // これらは それぞれ O(log N)で求めることができ, O(NlogN)で求めることができる

    def upperBounds(A: Array[Int], b: Int): Int = {
      def recursive(l: Int, r: Int): Int =
        if (r - l > 1) {
          val mid = l + (r - l) / 2
          if (A(mid) >= b) recursive(l, mid)
          else recursive(mid, r)
        } else l
      recursive(-1, N)
    }

    def lowerBounds(C: Array[Int], b: Int): Int = {
      def recursive(l: Int, r: Int): Int =
        if (r - l > 1) {
          val mid = l + (r - l) / 2
          if (C(mid) <= b) recursive(l, mid)
          else recursive(mid, r)
        } else l
      recursive(-1, N)
    }

    val r = (0 until N).foldLeft(0L) { case (sum, i) =>
      sum + (upperBounds(A, B(i)) + 1L) * (lowerBounds(C, B(i)) + 1L)
    }

    println(r)
  }

}


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

int main(){
  int n;
  scanf("%d",&n);
  vector<double> a(110,0);
  for(int i=0; i<n; i++){
    scanf("%lf",&a[i]);
  }
  double s = 0;
  for(int i=0; i<n; i++){
    s += 1/a[i];
  }
  printf("%lf\n",1/s);
}

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 int ll;
typedef unsigned long long int sll;
typedef long double ld;
#define A 1000000007ll
#define D 100000000000000ll
#define B 998244353ll
#define C 1000000000000000000ll
#define M 4000
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define oset tree<pair<ll,ll>, null_type,less_equal<pair<ll,ll>>, rb_tree_tag,tree_order_statistics_node_update> 
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define mxe(v) *max_element(v.begin(),v.end())
#define mne(v) *min_element(v.begin(),v.end())
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#define ve vector
#define br break
#define PI acos(-1)
#define subt cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n" 

ll parent[100005],siz[100005],cof[100005],ans[100005];

void make_set(ll v) {
    parent[v] = v;
    siz[v]=1;
}

ll find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v]=find_set(parent[v]);
}

void union_sets(ll a, ll b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b)
    {
        siz[a]+=siz[b];
        parent[b] = a;
    }
}

int main() 
{
    FAST;
    ll n,m,k;
    cin>>n>>m>>k;
    for(int i=0;i<=n;i++)
        make_set(i);
    ll a,b;
    for(int i=0;i<m;i++)
    {
        cin>>a>>b;
        cof[a]++;
        cof[b]++;
        union_sets(a,b);
    }
    for(int i=1;i<=n;i++)
        ans[i]=siz[find_set(i)]-cof[i]-1;
    for(int i=0;i<k;i++)
    {
        cin>>a>>b;
        if(find_set(a)==find_set(b))
        {
            ans[a]--;
            ans[b]--;
        }
    }
    for(int i=1;i<=n;i++)
        cout<<ans[i]<<' ';
    subt;
    return 0;
}

Measured memory_bytes: 4608
#include <iostream>
#include <algorithm>

using namespace std;

int lgpow(int a, int b, const int& MOD) {
    int sol = 1;

    while (b) {
        if (b & 1) {
            sol = (sol * 1LL * a) % MOD;
        }

        a = (a * 1LL * a) % MOD;
        b >>= 1;
    }

    return sol;
}

int invMod(int x, int MOD) {
    return lgpow(x, MOD - 2, MOD);
}

long long C(int n, int k, int MOD, int f[]) {
    if (n < k) {
        return 0;
    }

    return (((f[n] * 1LL * invMod(f[n - k], MOD)) % MOD) * 1LL * invMod(f[k], MOD)) % MOD;
}

int main()
{
    ios::sync_with_stdio(false);

    int n;
    cin >> n;

    int f[n + 1], v[n + 1], ap[n + 1];
    fill(ap + 1, ap + n + 1, 0);

    const int MOD = (const int)1e9 + 7;
    int ourDistance = 0;

    f[0] = 1;
    for (int i = 1; i <= n + 1; i++) {
        f[i] = (f[i - 1] * 1LL * i) % MOD;
        cin >> v[i];
        if (ap[v[i]] == 0) {
            ap[v[i]] = i;
        }
        else {
            ourDistance = i - ap[v[i]];
        }
    }

    for (int i = 1; i <= n + 1; i++) {
        int res = C(n + 1, i, MOD, f);
        res -= C(n - ourDistance, i - 1, MOD, f);

        if (res < 0) res += MOD;

        cout << res << "\n";
    }

    return 0;
}


Measured memory_bytes: 2432
N = int(input())
XL = sorted(list(map(int, input().split())) for _ in range(N))

i, j = 0, 1
count = N
while j < N:
  if XL[i][0] + XL[i][1] > XL[j][0] - XL[j][1]:
    if XL[i][0] + XL[i][1] < XL[j][0] + XL[j][1]:
      j += 1
    else:
      i, j = j, j + 1
    count -= 1
  else:
    i, j = j, j + 1
print(count)


Measured memory_bytes: 27872
l, r = map(int, input().split())
#print(l,r)

best = 2019
for i in range(l, min(r,l+2019)):
	for j in range(l+1,min(r+1,l+2019+1)):
		if i*j % 2019 < best:
			best = i*j % 2019

print(best)

Measured memory_bytes: 3060
#include <stdio.h>

void Sub(int total, int total2, int total3);
int main(void) {
	int a, b, c, x, y, total = 0, total2 = 0, total3 = 0;
	scanf("%d %d %d %d %d", &a, &b, &c, &x, &y);
	total = a * x + b * y;
	total2 = c * 2 * (x > y ? x : y);
	total3 = c * 2 * (x < y ? x : y) + a * (x - (x < y ? x : y)) + b * (y - (x < y ? x : y));
	//printf("%d %d %d\n", total, total2, total3);
	Sub(total, total2, total3);
	return 0;
}

void Sub(int total, int total2, int total3)
{
	int min = total;
	
	if(min>total2) min = total2;
	if(min>total3) min = total3;
	printf("%d\n", min);
}

Measured memory_bytes: 128
using System;
class FiveVariables
    {
        static void Main(string[] args)
        {
            string[] input= Console.ReadLine().Split();
            int[] x = new int[input.Length];
            int i;
            for(i = 0; i < input.Length; i++)
            {
                x[i] = int.Parse(input[i]);
                if (x[i] == 0)
                {
                    Console.WriteLine(i + 1);
                    break;
                }
            }
        }
    }

Measured memory_bytes: 27392
#include<stdio.h>
int main()
{
	int h, w;
	int i, j;
	for (;;)
	{
		scanf("%d %d", &h, &w);
		if (h == 0 && w == 0)
			break;
		for (i = 0; i < h; i++)
		{
			for (j = 0; j < w; j++)
				printf("#");
			printf("\n");
		}
		printf("\n");
	}
	return 0;
}


Measured memory_bytes: 2044
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <utility>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cassert>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;

//const long double PIL = 3.141592653589793238462643383279502884L;
//const double PI = 3.14159265358979323846;

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<pair<int,int>> vii;
#define sz(a) int((a).size())
#define all(c) (c).begin(), (c).end()

int main() {
	//~ ios::sync_with_stdio(0);
	//~ cin.tie(0);
	int a, b;
	cin >> a >> b;
	if (1 <= a && a <= 9 && 1 <= b && b <= 9)
		cout << (a*b) << endl;
	else
		cout << -1 << endl;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include<iostream>
using namespace std;

#define int long long int
#define all(x) x.begin(),x.end()
#define endl '\n'

#ifndef ONLINE_JUDGE
template<typename T>		
void __p(T a) {
  cerr<<a;
}
template<typename T, typename F>
void __p(pair<T, F> a) {
  cerr<<"[";
  __p(a.first);
  cerr<<",";
  __p(a.second);
  cerr<<"]";
}
template<typename T>
void __p(std::vector<T> a) {
  cerr<<"[";
  for(auto it=a.begin(); it<a.end(); it++)
    __p(*it),cerr<<",]"[it+1==a.end()];
}
template<typename T, typename ...Arg>
void __p(T a1, Arg ...a) {
  __p(a1);
  __p(a...);
}
template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
  cerr<<name<<" : ";
  __p(arg1);
  cerr<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
  int bracket=0,i=0;
  for(;; i++)
    if(names[i]==','&&bracket==0)
      break;
    else if(names[i]=='(')
      bracket++;
    else if(names[i]==')')
      bracket--;
  const char *comma=names+i;
  cerr.write(names,comma-names)<<" : ";
  __p(arg1);
  cerr<<" | ";
  __f(comma+1,args...);
}
#define trace(...) cerr<<"Line:"<<__LINE__<<" ", __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...)
#endif

const int INF = 1e9+5;

void test_case(){
	int n;
	cin>>n;
	vector<vector<int>> a(n,vector<int> (3)),dp(n,vector<int> (3));
	for(int i=0;i<n;i++){
		for(int j=0;j<3;j++){
			cin>>a[i][j];
		}
	}
	for(int i=0;i<3;i++){
		dp[0][i]=a[0][i];
	}
	for(int i=1;i<n;i++){
		for(int j=0;j<3;j++){
			for(int k=0;k<3;k++){
				if(j==k){
					continue;
				}
				dp[i][j]=max(dp[i][j],dp[i-1][k]);
			}
			dp[i][j]+=a[i][j];
		}
	}
	cout<<max({dp[n-1][0],dp[n-1][1],dp[n-1][2]});
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
 
    int T=1;
    //cin>>T;
    for(int TT=1; TT<=T; TT++){
        test_case();
    }

    cerr<<endl<<"Time : "<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n";

    return 0;
}


Measured memory_bytes: 14268
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    int n, k;
    public static void main(String[] args) {
        Main m = new Main();
        m.read();
        m.solve();
    }

    private void read() {
        Scanner sc = new Scanner(System.in);
        k = sc.nextInt();
        n = sc.nextInt();
    }

    private void solve() {
        if (k % 2 == 0) {
            StringBuilder sb = new StringBuilder();
            sb.append(k / 2);
            for (int i = 1; i < n; i++) {
                sb.append(" ");
                sb.append(k);
            }
            System.out.println(sb.toString());
            return;
        }
        int[] ns = new int[n];
        int cnt = n  / 2;
        Arrays.fill(ns, (k + 1) / 2);
        int trg = n - 1;
        for (int i = 0; i < cnt; i++) {
            while (trg >= 0 && ns[trg] == 0) trg--;
            if (ns[trg] == 1) {
                ns[trg] = 0;
            }
            else {
                ns[trg]--;
                for (int j = trg + 1; j < n; j++) {
                    ns[j] = k;
                    trg++;
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int n: ns)
            if (n != 0)
                sb.append(n + " ");
        System.out.println(sb.toString().trim());
    }
}


Measured memory_bytes: 48008
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
#define rep(i,x) for(ll i = 0; i < (ll)(x); i++)
#define pb push_back
#define eb emplace_back
#define debug(x) cerr << #x << ": " << (x) << "\n";
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<vector<ll>>> vvvl;
const ll INF = numeric_limits<ll>::max()/4;
const ll MOD = 1e9+7;
const int n_max = 1e5+10;


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

int main(){
    ll n; cin >> n;
    vector<ll> s(n);
    rep(i,n) cin >> s[i];
    vector<ll> dp(11000, 0);
    dp[0] = 1;
    rep(i,n){
        for(int j = 10999; 0 <= j; j--){
            if(j - s[i] >= 0 && dp[j - s[i]])dp[j] = 1;
        }
    }

    ll max_ = 0;
    rep(i,11000)if(i % 10 != 0 && dp[i])chmax(max_, i);
    cout << max_ << endl;
}

Measured memory_bytes: 384
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define cinf(n,x) for(int i=0;i<(n);i++)cin>>x[i];
#define ft first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define mod 1000000007
using namespace std;
typedef long long ll;
template<class T> using V=vector<T>;
using Graph = vector<vector<int>>;
using P=pair<ll,ll>;
typedef unsigned long long ull;
typedef long double ldouble;
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; }
//V,P(大文字)使用不可
//乗算の際にオーバーフローに注意せよ！！（適切にmodをとれ）
//制約をよく読め！

const ll INF=1e18;

signed main(){
    V<double> x(2),y(2);
    rep(i,2) cin>>x[i]>>y[i];
    int q;
    cin>>q;
    while(q--){
        double a,b;
        cin>>a>>b;
        double t=((x[0]-x[1])*(x[0]-a)+(y[0]-y[1])*(y[0]-b))/(pow(x[1]-x[0],2)+pow(y[1]-y[0],2));
        double xx=x[0]+t*(x[1]-x[0]);
        double yy=y[0]+t*(y[1]-y[0]);
        double px=xx-a,py=yy-b;
        cout<<fixed<<setprecision(10)<<a+2*px<<' '<<b+2*py<<endl;
    }
}


Measured memory_bytes: 3300
// Problem : D - Leaping Tak
// Contest : AtCoder - AtCoder Beginner Contest 179
// URL : https://atcoder.jp/contests/abc179/tasks/abc179_d
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

/*ヽ｀、ヽ｀｀、ヽ｀ヽ｀、、ヽ ｀ヽ 、ヽ｀🌙｀ヽヽ｀ヽ、ヽ｀
ヽ｀、ヽ｀｀、ヽ 、｀｀、 ｀、ヽ｀ 、｀ ヽ｀ヽ、ヽ ｀、ヽ｀｀、
ヽ、｀｀、｀、ヽ｀｀、 、ヽヽ｀、｀、、ヽヽ、｀｀、 、 ヽ｀、
ヽ｀｀、 ヽ｀ヽ｀、、ヽ ｀ヽ 、 🚶ヽ｀｀｀｀ヽヽヽ｀、、ヽ｀、、ヽ*/
#include <bits/stdc++.h> 
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
 
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long   ll;
typedef long double ld;
typedef complex< ld > cd;
 
typedef pair<int, int> pi;
typedef pair<ll, ll>   pl;
typedef pair<ld, ld>   pd;
 
typedef vector< int > vi;
typedef vector< ld >  vd;
typedef vector< ll >  vl;
typedef vector< pi >  vpi;
typedef vector< pl >  vpl;
typedef vector< cd >  vcd;
 
#define l00p(i, a, b) for (int i=a; i<(b); i++)
#define loop(i, a)    for (int i=0; i<(a); i++)
#define rep1(i, a, b) for (int i = (b)-1; i >= a; i--)
#define rep(i, a)     for (int i = (a)-1; i >= 0; i--)
#define trav(a, x)    for (auto& a : x)
#define uid(a, b)     uniform_int_distribution<int>(a, b)(rng)
#define vt vector
#define bug(x) cout<<#x<<"="<<x<<endl;

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f  first
#define s  second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ins insert
#define MOD 998244353
 
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ld pii=3.14159265359; 
//const int MOD = 1000000007;
const char cl = '\n';
const ll INF = 1e18;
const int MX = 100001; //check the limits, dummy

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); 
	ll n,k;
	cin>>n>>k;
	vpl units;
	loop(i,k){
		int a,b;
		cin>>a>>b;
		units.pb({a,b});
	}
	vl pref(n+1),dp(n+1);
	pref[1]=1;
	dp[1]=1;
	for(ll i=2;i<n+1;i++){
		trav(j,units){
			dp[i]=dp[i]-pref[max(0ll,i-j.s-1)]+pref[max(0ll,i-j.f)];
			dp[i]%=MOD;
		}
		pref[i]=pref[i-1]+dp[i];
	}
	cout<<dp[n];
	return 0;
}
// read the question correctly (ll vs int)
// template by bqi343


Measured memory_bytes: 6380
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <fstream>
#include<cstdio>
#include<iomanip>

#define REP(i, n) for(int i=0;i<n;i++)

using namespace std;

typedef long long ll;
typedef unsigned long ul;
typedef long double ld;


int main() {
    ll N, D;
    cin >> N >> D;
    if (N % (2 * D + 1) == 0) {
        cout << N / (2 * D + 1);
    } else {
        cout << N / (2 * D + 1) + 1;
    }
    return 0;
}





Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cstring>
#include <algorithm>
#include <math.h>

using namespace std;

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

#define FOR(i,n,m) for(int i=n; i<(int)m; i++)
#define ROF(i,n,m) for(int i=n; i>(int)m; i--)
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define F first
#define S second
#define ri(a) scanf("%d",&a)
#define rii(a,b) ri(a),ri(b)
#define riii(a,b,c) rii(a,b),ri(c)
#define lri(a) scanf("%lld",&a)
#define lrii(a,b) lri(a),lri(b)
#define ms(obj,val) memset(obj,val,sizeof(obj))
#define all(x) x.begin(),x.end()
#define debug true
#define dprintf debug && printf

const int INF = 0x3f3f3f3f;
const ll INFLL = 1e18;
const int MOD = 1e9+7;
const int MAXN = 2e5+5;

vi pos, neg;
int n, k;

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

    rii(n, k);
    FOR(i,0,n){
        int x;
        ri(x);
        if(x == 0) k--;
        else if(x > 0) pos.pb(x);
        else neg.pb(-x);
    }

    if(k == 0) {printf("0\n"); return 0;}
    int ans = INF;
    reverse(all(neg));
    FOR(i,0,neg.size()){
        int aux = neg[i];
        if(i + 1 >= k) ans = min(ans, aux);
        else if(k - 2 - i < pos.size()) ans = min(ans, 2*aux + pos[k - 2 - i]);
    }
    FOR(i,0,pos.size()){
        int aux = pos[i];
        if(i + 1 >= k) ans = min(ans, aux);
        else if(k - 2 - i < neg.size()) ans = min(ans, 2*aux + neg[k - 2 - i]);
    }
    printf("%d\n", ans);

    return 0;
}


Measured memory_bytes: 1020
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int x=sc.nextInt(),y=sc.nextInt();
		int o=sc.nextInt();
		int[] X=new int[x+1];
		int[] Y=new int[y+1];
		while(o-->0){
			
			int a=sc.nextInt(),b=sc.nextInt();
			int test = sc.nextInt();
			if(test==1){
				for(int i=0;i<=a;i++){
					X[i] = 1;
				}
			}
			if(test==2){
				for(int i=a+1;i<=x;i++){
					X[i] = 1;
				}
			}
			if(test==3){
				for(int i=0;i<=b;i++){
					Y[i] = 1;
				}
			}
			if(test==4){
				for(int i=b+1;i<=y;i++)
					Y[i] = 1;
			}
		}
		int xcan = 0,ycan = 0;
		for(int i=1;i<x+1;i++){
			if(X[i]==0)
				xcan++;
		}
		for(int i=1;i<y+1;i++){
			if(Y[i]==0)
				ycan++;
		}
		System.out.print(xcan*ycan);
	}
}


Measured memory_bytes: 23764
#include<stdio.h>
int main()
{
	int a,b,c,d;

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

	if(a<c)
		a=c;
	if(b>d)
		b=d;
	if(b-a<0)
		printf("0");
	else
		printf("%d",b-a);
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<double,int>;
const ll inf = numeric_limits<ll>::max()/3;

int n;
vector< string > grid;
int memo[310][310] = {};

bool check(int a,int b){
  for(int i = 0;i < n;++i){
    for(int j = 0;j < n;++j){
      int y1 = (i + n - a) % n;
      int x1 = (j + n - b) % n;
      int y2 = (j + n - a) % n;
      int x2 = (i + n - b) % n;
      if(grid[y1][x1] != grid[y2][x2])
        return false;
    }
  }
  return true;
}


int main(void){
  cin >> n;
  grid.resize(n);
  for(int i = 0;i < n;++i){
    cin >> grid[i];
  }
  ll cnt = 0;
  for(int i = 0;i < n;++i){
    for(int j = 0;j < n;++j){
      if(i > 0 && j > 0 && memo[i-1][j-1]){
        memo[i][j] = memo[i-1][j-1];
      }else{
        memo[i][j] = (check(i,j) ? 1 : -1);
      }
      if(memo[i][j] == 1)
        ++cnt;
    }
  }
  cout << cnt << endl;
  return 0;
}



Measured memory_bytes: 768
n, m = map(int, input().split())
flag = [False] * n
quan = [1] * n
flag[0] = True
for i in range(m):
    x, y = map(int, input().split())
    x, y = x - 1, y - 1
    if flag[x]:
        flag[y] = True
    quan[x] -= 1
    quan[y] += 1
    if quan[x] == 0:
        flag[x] = False

print(len(list(filter(lambda x: x == True, flag))))


Measured memory_bytes: 5540
#include <bits/stdc++.h>
#define exrep(i, a, b) for(long long i = a; i <= b; i++)
#define rep(i,n)for(long long i=0;i<(long long)(n);i++)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
const ll MOD=1e9+7;
const ll INF=1e18;
const int MAX=510000;
const double pi=acos(-1);
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};


int main(){
  cin.tie(0);
  ios::sync_with_stdio(false); 
  
  ll n,m,x;
  cin >> n >> m >> x;
  x--;
  vector<int>a(n,0);
  rep(i,m){
    int c;
    cin >> c;
    c--;
    a[c]++;
  }
  ll cost1=0,cost2=0;
  exrep(i,0,x){
    if(a[i])cost1++;
  }
  exrep(i,x,n-1){
    if(a[i])cost2++;
  }
  cout <<min(cost1,cost2) << endl;
  
}


Measured memory_bytes: 256
import queue

K = int(input())

Q = queue.Queue()
for i in range(1, 10):
    Q.put(i)

for i in range(K-1):
    x = Q.get()
    if x%10 != 0:
        Q.put(10*x+x%10-1)
    Q.put(10*x+x%10)
    if x%10 != 9:
        Q.put(10*x+x%10+1)
print(Q.get())

Measured memory_bytes: 57428
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b;
    cin>>a>>b;
    if(a<b) swap(a,b);
    while(1){
        if(a%b==0){
            cout<<b<<endl;
            break;
        }
        else{
            int c=b;
            b=a%b;
            a=c;
        }
        
    }
}


Measured memory_bytes: 3060