akhauriyash/Code-Regression huggingface dataset:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
#https://note.nkmk.me/python-union-find/

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())
n,m=MI()
u=UnionFind(n)
for i in range(m):
    a,b,c=MI()
    u.union(a-1,b-1)
print(u.group_count())
    

Measured memory_bytes: 13952
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
  int n;
  cin >> n;
  vector<int>a(n);
  for(int i=0; i<n; i++){
    cin >> a.at(i);
  }
  sort(a.begin(),a.end());
  cout << a.at(n-1)-a.at(0) << endl;
  
}


Measured memory_bytes: 256
n,k = map(int,input().split())
l = [list(map(int,input().split())) for i in range(n)]
l.sort()
s = bin(k)[2:]
s = s[::-1]
m = len(s)
dp = [0]*(m+1)

for i,v in l:
    if i > k:
        break
    check = True
    for j in range(m-1,-1,-1):
        
        if ((i>>j)&1) and s[j] == "0":
            check = False
            break
        if s[j] == "0":
            continue
        if s[j] == "1" and (not (i>>j)&1):
            dp[j] += v
    if check:
        dp[-1] += v
    
print(max(dp))




Measured memory_bytes: 27676
from collections import defaultdict

N, M = map(int, input().split())
drinks = defaultdict(int)

for _ in range(N):
    A, B = map(int, input().split())
    drinks[A] += B

drinks = sorted(drinks.items(), key = lambda x : x[0])
cnt = 0
price = 0

for k, v in drinks:
    purchases = min(v, M - cnt)
    cnt += purchases
    price += purchases * k

print(price)


Measured memory_bytes: 24540
/*
Original problem: https://atcoder.jp/contests/abc136/tasks/abc136_d
Author: sammochen
*/

#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"

using namespace std;

#define REP(x,l,u) for(ll x = l;x<u;x++)
#define RREP(x,l,u) for(ll x = l;x>=u;x--)

#define PII pair<int,int>
#define PLL pair<ll,ll>
#define MP make_pair

typedef  long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
typedef vector<ll> VLL;
typedef vector<int> VI;

namespace SOLVE {
    void main() {
        string s;
		cin >> s;
		VI ans(s.size());
		// count R streaks
		int l = 1; // length
		REP(i,1,s.size()){
			if (s[i] == 'L' && s[i] != s[i-1]) {
				ans[i] += l/2;
				ans[i-1] += l - l/2;
			}
			if (s[i] == 'R' && s[i] != s[i-1]) {
				l = 1;
			}
			if (s[i] == 'R' && s[i] == s[i-1]) {
				l++;
			}
		}

		// L streaks
		l = 1;
		RREP(i,(int)s.size() - 2,0){
			if (s[i] == 'R' && s[i] != s[i+1]) {
				ans[i] += l/2;
				ans[i+1] += l - l/2;
			}
			if (s[i] == 'L' && s[i] != s[i+1]) {
				l = 1;
			}
			if (s[i] == 'L' && s[i] == s[i+1]) {
				l++;
			}
		}
		REP(i,0,s.size()) {
			cout << ans[i];
			if (i == s.size() - 1) {
				cout << endl;
			} else {
				cout << " ";
			}
		}

    }
}


signed main() {
	int t;
	t = 1;
	// cin >> t;
	while (t--) {
		SOLVE::main();
	}

	return 0;
}

Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {

	void main() {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int [n];
		
		for(int i = 0; i <a.length; i++) {
			a[i] = sc.nextInt();
		}
		System.out.print(a[a.length-1]);
		for(int i = a.length-2; i >=0; i--) {
			System.out.print(" " + a[i]);
		}
		System.out.println();
	}
	
	public static void main(String[] args) {
		new Main(). main();
	}

}



Measured memory_bytes: 26452
# -*- coding: utf-8 -*-


def main():
    """Function."""
    n = int(input())

    save = [2, 1]
    for _ in range(n-1):
        dum = save[-1] + save[-2]
        save.append(dum)

    print(save[-1])


if __name__ == "__main__":
    main()


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

int main() {
  char c;
  cin >> c;

    if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
      cout << "vowel" << endl;
    }
    
    else {
      cout << "consonant" << endl;
    }
}




Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int check(int a,int b){
	if(a<10&&b<10&&a>0&&b>0)return a*b;
	else return -1;
}
int main(){
	int a,b;
	cin>>a>>b;
	cout<<check(a,b);
	return 0;
} 

Measured memory_bytes: 3588
//#pragma warning disable
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System;
using System.Numerics;
using System.Threading.Tasks;
using static System.Math;
using static System.Console;
class Z { static void Main() => new K(); }
class K
{
	int F() => int.Parse(ReadLine());
	long FL() => long.Parse(ReadLine());
	int[] G() => ReadLine().Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray();
	long[] GL() => ReadLine().Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries).Select(long.Parse).ToArray();
	public const int MOD = 1000000007;
	public K()
	{
		SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
		Solve();
		Out.Flush();
	}
	void Solve()
	{
		var I = G();
		int A = I[0], B = I[1], C = I[2], D = I[3], E = I[4], F = I[5];
		var sugar = new bool[F + 1];
		sugar[0] = true;
		for (var i = C; i <= F; i++) sugar[i] = sugar[i - C] || (i >= D && sugar[i - D]);
		int mA = F / (100 * A), mB = F / (100 * B);
		int gW = 100 * A, gS = 0;
		for (var a = 0; a <= mA; a++)
			for (var b = 0; b <= mB; b++)
			{
				var w = a * A + b * B;
				var m = Min(F - 100 * w, E * w);
				if (m <= 0) continue;
				var s = m;
				while (!sugar[s]) s--;
				if (s * gW > gS * w * 100)
				{
					gW = w * 100;
					gS = s;
				}
			}
		WriteLine("{0} {1}", gW + gS, gS);
	}
}


Measured memory_bytes: 13396
#include <algorithm>
#include <bitset>
#include <cfloat>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
#define int long long
#define ll long long
#define eps LDBL_EPSILON
#define mod 1000000007
#define int long long
#define double long double
#define INF LLONG_MAX/10
#define P pair<int,int>
#define prique priority_queue
using namespace std;
signed main() {
  int n,a,b;
	cin >> n >> a >> b;
	cout << min(n * a, b) << endl;
	return 0;
}

Measured memory_bytes: 764
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;cin >> n;
	vector<int> a(n);
	rep(i,n) cin >> a.at(i);
	ll ans=0;
	rep(i,n-1){
		if(a[i]&1==1 && a[i+1]>0){
			ans++;
			a[i]--;
			a[i+1]--;
		}
	}
	rep(i,n){
		ans+=a[i]/2;
		a[i]%=2;
	}
	cout << ans << endl;
}

Measured memory_bytes: 640
from collections import defaultdict


def main():
    _ = input()
    
    n_dic = defaultdict(lambda: 0)
    for x in input().split():
        n_dic[int(x)] += 1

    minv = 0
    for k, v in n_dic.items():
        if k > v:
            minv += v
        elif k < v:
            minv += v-k
    print(minv)


if __name__ == '__main__':
    main()

Measured memory_bytes: 23668
#include <iostream>
#include <cstdio>
#include <utility>
#include <vector>
#include <array>
#include <algorithm>
#include <string>
#include <cmath>
#define y0 y3487465
#define y1 y8687969
#define j0 j1347829
#define j1 j234892
#define next asdnext
#define prev asdprev
#define INF 2000000000
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
using namespace std;
typedef long long ll;
int gcd(int a, int b){return b ? gcd(b, a % b): a;}
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

int n, k;

int main()
{
    cin >> n >> k;
    if(k%2==1){
        // k is odd
        // a, b, c === 0 mod K
        ll m = n / k;
        cout << m*m*m << endl;
    }
    else{
        // k is even
        // a, b, c === 0 mod K or K/2 mod K
        ll m1 = n / k;
        ll m2 = (n + k/2) / k;
        cout << m1*m1*m1 + m2*m2*m2 << endl;
    }
    return 0;
}


Measured memory_bytes: 256
I,*U=N,*D=9**9,
P,*L='x+y,',
M,*R='x-y,',
for t in[*open(0)][1:]:*z,u=t.split();exec(u+'+=[*map(int,z)],')
for*A,S in(D,U,'x,y,'),(L,R,'y,x,'),(U,R,P+M),(L,D,P+M),(L,U,M+P),(D,R,M+P):
 n=-I
 for x,y,r in eval('sorted((%sQ)for Q,P in enumerate(A)for x,y in P)'%S):
  if r:n,p=x,y
  elif x==n:N=min(N,y-p)
print(N%I*5or'SAFE')

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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define UB upper_bound
#define LB lower_bound
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

int n, m;
bool e[8][8];

#define F(i) for(c[i] = 0; c[i] < n; c[i]++)

int main() {
	cin >> n >> m;
	inc(i, m) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		e[a][b] = true;
		e[b][a] = true;
	}
	
	int ans = 0;
	
	int c[8];
	F(0) {
	F(1) {
	F(2) {
	F(3) {
	F(4) {
	F(5) {
	F(6) {
	F(7) {
		bool flag = (c[0] == 0);
		inc(i, 8) {
			if(i < n) { flag &= (inID(c[i], 0, n)); }
			else { flag &= (c[i] == 0); }
		}
		inc(i, n) {
		inc(j, i) {
			if(c[i] == c[j]) { flag = false; }
		}
		}
		if(! flag) { continue; }
		
		flag = true;
		inc(i, n - 1) {
			flag &= e[ c[i] ][ c[i + 1] ];
		}
		if(flag) { ans++; }
	}}}}}}}}
	
	cout << ans << endl;
	
	return 0;
}


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

int main() {
  char c;
  cin >> c;
  if (c == 'a' || c == 'i' || c == 'e' || c == 'o' || c == 'u')
    cout << "vowel" << endl;
  else
    cout << "consonant" << endl;
}

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

inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	for (; ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') f = -1;
	for (; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
	return x * f;
}

const int N = 1e3 + 5;
vector<int> G[N], ans, cur;
bool vis[N];

void dfs(int u)
{
	vis[u] = 1;
	cur.push_back(u);
	for (int v : G[u])
		if (cur[0] == v && (!ans.size() || ans.size() > cur.size())) ans = cur;
		else if (!vis[v]) dfs(v);
	
	cur.pop_back();
}

int main()
{
	int n = read();
	int m = read();
	for (int i = 1; i <= m; ++i)
	{
		int u = read(), v = read();
		G[u].push_back(v);
	}
	
	for (int i = 1; i <= n; ++i) 
		memset(vis, 0, sizeof(vis)), dfs(i);
	
	if (ans.size() == 0) return puts("-1"), 0;
	printf("%d\n", ans.size());
	for (int i : ans) printf("%d\n", i);
	
	return 0;
}

Measured memory_bytes: 384
use proconio::{input, fastout};

pub struct UnionFind {
    parent: Vec<usize>,
    rank: Vec<usize>,
    size: Vec<usize>,
}

impl UnionFind {
    pub fn new(n: usize) -> Self {
        let parent = (0..n).collect::<Vec<usize>>();
        Self {
            parent,
            rank: vec![0; n],
            size: vec![1; n],
        }
    }

    pub fn root(&mut self, x: usize) -> usize {
        if x == self.parent[x] {
            x
        } else {
            self.parent[x] = self.root(self.parent[x]);
            self.parent[x]
        }
    }

    pub fn unite(&mut self, a: usize, b: usize) {
        let ra = self.root(a);
        let rb = self.root(b);
        if self.rank[ra] > self.rank[rb] {
            self.parent[rb] = ra;
            self.size[ra] += self.size[rb];
        } else if self.rank[ra] < self.rank[rb] {
            self.parent[ra] = rb;
            self.size[rb] += self.size[ra];
        } else if ra != rb {
            self.parent[rb] = ra;
            self.size[ra] += self.size[rb];
            self.rank[ra] += 1;
        }
    }

    pub fn size(&mut self, x: usize) -> usize {
        let rx = self.root(x);
        self.size[rx]
    }

    pub fn same(&mut self, a: usize, b: usize) -> bool {
        self.root(a) == self.root(b)
    }
}

#[fastout]
fn main() {
    input! {
        n: usize,
        q: usize,
        tuv: [(usize, usize, usize); q],
    }

    let mut uf = UnionFind::new(n+1);

    for (t, u, v) in tuv {
        if t == 0 {
            uf.unite(u, v);
        } else if t == 1 {
            let ans = if uf.same(u, v) { 1 } else { 0 };
            println!("{}", ans);
        }
    }
}


Measured memory_bytes: 11908
n,m = map(int,input().split())
ls = []
switch = [(i+1) for i in range(n)]
ls = [list(map(int,input().split())) for i in range(m)]
p = list(map(int,input().split()))

pattern = []
for i in range(2**n):
    pattern.append(list(bin(i)[2:].zfill(n)))

ans = 0

for i in pattern:
    turn = []
    on = 0
    for j in range(n):
        if i[j] == '1':
            turn.append(switch[j])
    for k in range(m):
        count = 0
        for l in range(1,ls[k][0]+1):
            if ls[k][l] in turn:
                count += 1
        if count % 2 == p[k]:
            on += 1
    if on == m:
        ans += 1
            
print(ans)

Measured memory_bytes: 3188
#include<iostream>
using namespace std;
int main() {
	int D, T , S;
	cin >> D >> T >> S;
	if (T * S >= D) {
		cout << "Yes" << endl;
	}
	else if (T * S < D) {
		cout << "No" << endl;
	}
	return 0;
}

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

int main() {
  char c;
  cin >> c;
  string A; A="aiueo";
  int q;q=0;
  
  for (int i=0;i<5;i++){
  char a;a=A.at(i);
   if (c == a){
     cout << "vowel" << endl;
     q++;
   }
  }
  if(q!=1) {
    cout << "consonant" << endl;
  }
}


Measured memory_bytes: 3656
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

ll dp[2][110][10];  /* dp[id][i+1][j] : 先頭からi桁目までで0でない数がj個現れるs以下の数の個数。
                                       ただし、id = 0 のとき現時点でsと等しい。
                                       id = 1 のとき現時点でsより小さいことが確定。 */

int main() {
    string s;
    ll k;
    cin >> s >> k;
    ll m = s.size();  // sはm桁とする
    
    dp[0][0][0] = 1;
    rep(id, 2) {
        rep(i, m) {
            rep(j, 4) {
                ll lim = s[i] - '0';  //  先頭からi桁目にはlim以下の数を置ける
                if(id) {
                    lim = 9;
                }
                exrep(x, 0, lim) {  // 先頭からi桁目にxを置くとする
                    dp[id || x < lim][i+1][j + (x != 0)] += dp[id][i][j];
                }
            }
        }
    }
    
    ll ans = (dp[0][m][k] + dp[1][m][k])%mod;
    
    out(ans);
    re0;
}

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

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

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

typedef long long ll;
typedef long double R;
const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max(x,0.0L));}

const int dx[8]={1,0,-1,0,1,-1,-1,1};
const int dy[8]={0,1,0,-1,1,1,-1,-1};
const int NMAX=100000;
const int KMAX=100;
int N, K;
vector<int> h(NMAX);
int dp[NMAX+1];

int main() {
  cin >> N >> K;
  for(int i = 0; i < N; ++i) {
    cin >> h[i];
  }
  for(int i = 0; i <= NMAX; ++i) {
    dp[i] = (int)1e9;
  }
  dp[0] = 0;
  for(int i = 0; i < N; ++i) {
    for(int j = i+1; j <= i+K; ++j) {
      if(j < N) dp[j] = min(dp[j], dp[i] + abs(h[i] - h[j]));
    }
  }
  cout << dp[N-1] << endl;

  return 0;
}


Measured memory_bytes: 1024
#include <set>
#include <numeric>
#include <vector>
#include <iostream>
using namespace std;

class UnionFind {
    vector<int> par, rank, size;
public:
    explicit UnionFind(int n) : par(n), rank(n, 0), size(n, 1) {
        iota(par.begin(), par.end(), 0);
    }

    int find(int i) {
        return (par[i] == i) ? i : (par[i] = find(par[i]));
    }

    void unite(int i, int j) {
        int x = find(i), y = find(j);
        if (x != y) {
            if (rank[x] < rank[y]) {
                par[x] = y;
                size[y] += size[x];
            } else {
                par[y] = x;
                size[x] += size[y];
                if (rank[x] == rank[y]) rank[x]++;
            }
        }
    }

    int card(int i) { return size[find(i)]; }
};

int main() {
    int n; cin >> n;
    int xy[n], xinv[n];
    for (int i = 0; i < n; i++) {
        int x, y; cin >> x >> y;
        xy[x-1] = y-1;
        xinv[x-1] = i;
    }
    set<pair<int, int> > s; // (y, x)
    UnionFind uf(n);
    for (int x = 0; x < n; x++) {
        pair<int, int> p = {xy[x], x};
        for (auto it = s.begin(); it != s.end() && it->first < xy[x]; ) {
            uf.unite(xinv[x], xinv[it->second]);
            if (p.first > it->first) p = *it;
            it = s.erase(it);
        }
        s.insert(p);
    }
    for (int i = 0; i < n; i++) cout << uf.card(i) << endl;
}


Measured memory_bytes: 11524
import math

n=int(input())

def prime_check(x): #x>=2
    if x==2:
        return True
    elif x%2==0:
        return False
    else:
        limit=int(math.sqrt(x))
        for factor in range(3,limit+1,2):
            if x%factor==0:
                return False
        return True

temp=11
count=0
L=[]
while True:
    if prime_check(temp):
        L.append(temp)
        count+=1
    
    if count==n:
        break
    else:
        temp+=10

print(*L)





Measured memory_bytes: 8812
# -*- coding: utf-8 -*-

n = int(input())
p = [int(e) for e in input().split()]

count = 0

for i in range(n-2):
    if p[i] < p[i+1] < p[i+2]:
        count += 1
    elif p[i] > p[i+1] > p[i+2]:
        count += 1

print(count)


Measured memory_bytes: 2940
r=99,n=98,t,s;
int c(int i,int j,int k){printf("< %d %d %d ",i,j,k);}
int a(int i,int j,int k){printf("+ %d %d %d ",i,j,k);}
int b(int i,int j,int k){a(i,j,r);c(n,r,r+1);a(k,r+1,k);}
int m(int i,int l,int j,int p,int k){for(t=0;t<l+p-1;++t){if(t)a(k,k,k);for(s=0;s<=t;++s)if(s<p&&s+l>t)b(i+t-s,j+s,k);}}
int d(int x,int i,int l,int j){for(t=0;t<l;++t){if(t)a(j+t-1,j+t-1,j+t);a(j+t,n,j+t);for(s=t;s+1<l;++s)a(j+s,j+s,j+s+1);c(j+l-1,x,i+t);a(j+t-1,j+t-1,j+t);a(j+t,i+t,j+t);}}
main(){puts("3930");a(0,1,n);c(2,n,n);a(0,n,3);a(1,n,4);d(3,5,30,36);d(4,36,30,67);m(5,30,36,30,2);}

Measured memory_bytes: 1576
import Data.List

solver::String->String->String->Int
solver [] _ _ = 0
solver (x:xs) (y:ys) (z:zs) = ((length.group.sort) [x,y,z])-1 + (solver xs ys zs)

main::IO()
main=do
  _<-getLine
  a<-getLine
  b<-getLine
  c<-getLine
  print (solver a b c)


Measured memory_bytes: 636
#include<iostream>
#include<vector>
using namespace std;
	vector<int> x,y;
	int n,a,b,s,t;
int rep(int now,int nx,int ny){
	int px,py,p=0;
	if(now!=-1){
		for(int i=0;i<3;i++)
			for(int j=0;j<3;j++)
				if(nx==x[now]-1+i&&ny==y[now]-1+j)
					p++;
		if(p==0)
			return 0;
	}
	if(now==n-1)
		return 1;
	for(int i=0;i<3;i++){
		px=nx+2;py=ny-1+i;
		if(px>=0&&px<=9&&py>=0&&py<=9){
			if(rep(now+1,px,py))
			return 1;
		}
		px=nx-2;py=ny-1+i;
		if(px>=0&&px<=9&&py>=0&&py<=9){
			if(rep(now+1,px,py))
			return 1;
		}
		px=nx-1+i;py=ny-2;
		if(px>=0&&px<=9&&py>=0&&py<=9){
			if(rep(now+1,px,py))
			return 1;
		}
		px=nx-1+i;py=ny+2;
		if(px>=0&&px<=9&&py>=0&&py<=9){
			if(rep(now+1,px,py))
			return 1;
		}
	}
	return 0;
}
void solve(){
	if(rep(-1,a,b))
	cout<<"OK"<<endl;
	else cout<<"NA"<<endl;
}
int main(){
	while(cin>>a>>b,a||b){
		cin>>n;
		for(int i=0;i<n;i++){
			cin>>s>>t;
			x.push_back(s);
			y.push_back(t);
		}
		solve();
		x.clear();
		y.clear();
	}
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = s; i < (int)(n); i++)
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using pii = pair<int, int>;

//const ll INF = 1e18L + 5;
//const int INF = 1e9 + 5;
//const double pi = 3.14159265358979323846;

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

	long double a, b, C;
	cin >> a >> b >> C;
	long double area = a * b * sin(C / 180  * acos(-1)) / 2;
	long double cir = a + b + sqrt(a * a + b * b - 2 * a * b * cos(C / 180 * acos(-1)));
	long double h = b * sin(C / 180 * acos(-1));
	printf("%.8Lf\n%.8Lf\n%.8Lf\n", area, cir, h);
}



Measured memory_bytes: 3492
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <unistd.h>
#include <math.h>
long long int ans=0;
#define  ll long long
//最大公約数
long long int getgcd(long long n, long long m)
{
  int r;
  if (n > m) {
    long long t = m;
    m = n;
    n = t;
  }
  while ((r = m % n) != 0) {
    m = n;
    n = r;
  }
return n;
}

//nの階乗を計算
long long factorial(long long n){
    long long int answer = 1;
while(n > 1){
  answer *= n;
  n--;
}
    return answer;
}

//組み合わせの数nCrを計算
long long calcNumOfCombination(long long  n, long long r){
    return factorial(n) / (factorial(r) * factorial(n-r));
}
 void yes(){
   printf("Yes\n");
 }

 void no(){
   printf("No\n");
 }

int main(int argc, char* argv[]){
	ll a = 0, b = 0,c=0,e=0;
  char h[1000];
  scanf("%lld %lld",&a,&b);
  ll g[a];
  for (int i = 0; i < a; i++) {
    g[i]=0;
  }
  for (int i = 0; i < b; i++) {
    scanf("%lld",&c);
    for (int j = 0; j < c; j++) {
      scanf("%lld",&e);
      g[e-1]=1;
    }
  }
  for (int i = 0; i < a; i++) {
    if (g[i]==0) {
      ans++;
    }
  }
  printf("%lld",ans);
  return 0;
}


Measured memory_bytes: 1732
f a c =
  if a `mod` c /= 0
           then (a `div` c) + 1
           else (a `div` c)

max' a b =
  if a >= b
  then a
  else b

ans (l:a:b:c:d:_) =
  let cc = f a c
      dd = f b d
  in
    l - max' cc dd
    

main = do
  c <- getContents
  let i = map read $ lines c :: [Int]
      o = ans i
  print o

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

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>
#include<iomanip>
#include<unordered_set>
#include<bitset>
#include<complex>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

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 (b < a) { a = b; return true; } return false; }

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

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

	int N;
	int A[210];
	int ans = 0;
	cin >> N;
	rep(i, 0, N)
	{
		cin >> A[i];
	}
	while (true)
	{
		bool ok = true;
		rep(i, 0, N)
		{
			if (A[i] % 2 == 1)ok = false;
			A[i] /= 2;
		}
		if (!ok)break;
		ans++;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 764
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma warning(disable : 4996)
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<time.h>
#include<random>
#include<array>


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)
#define FOR(i, m, n) for(int i = m;i < n;++i)
#define FORR(i, m, n) for(int i = m-1;i >= n;--i)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end())
#define ll long long
#define print(x) cout<<(x)<<'\n'
#define pe(x) cout<<(x)<<" "
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define lb(v,n) lower_bound(v.begin(), v.end(), (n))
#define ub(v,n) upper_bound(v.begin(), v.end(), (n))
#define int long long
//#define double long double
#define all(x) (x).begin(), (x).end()
#define print_space(v) REP(i,v.size())cout << v[i] << ((i == v.size() - 1) ? "\n" : " ")
template<typename T1, typename T2> inline void chmin(T1 & a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
typedef pair<int, int>P;
std::random_device rd;
std::mt19937 mt(rd());
constexpr int MOD = 998244353; constexpr int MAX = 200020;
const double pi = acos(-1); constexpr double EPS = 1e-8;
constexpr ll INF = 1e18;




int dp[2][100010];
int cnt[10001];
void solve() {
	int N; cin >> N;
	int p; cin >> p;
	string S; cin >> S;
	if (p < 100) {
		ll ans = 0;
		int c = 1;
		//dp[0][0] = 1;
		REP(i, N + 1) {
			int now = i % 2;
			int nxt = (now + 1) % 2;
			int num = S[i] - '0';
			ans += dp[now][0];
			if (i == N)break;
			REP(j, p)dp[nxt][j] = 0;
			dp[nxt][(num) % p]++;
			REP(j, p) {
				dp[nxt][(j * 10 + num) % p] += dp[now][j];
			}
		}
		print(ans);
	}
	else {
		int now = 0;
		int c = 1;
		ll ans = 0;
		cnt[0] = 1;
		REPR(i, N) {
			int num = S[i] - '0';
			now = (now + c * num) % p;
			//print(num);
			//print(c);
			//print(now);
			//if (now%p == 0)ans++;
			c = (c * 10) % p;
			ans += cnt[now];
			cnt[now]++;
		}
		//ans += cnt[0];
		print(ans);
	}
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	//int q; cin >> q;
	//while (q--)
	solve();
}



Measured memory_bytes: 720
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <ctime>
#include <cstring>
#include <functional>
#include <iostream>
#include <iomanip>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <regex>
#include <vector>

#define fix(n)          cout<<fixed<<setprecision(n)
#define rep(i,n)        for (int i = 0; i < (n); ++i)
#define sort(a)         sort((a).begin(), (a).end())
#define uniq(a)         SORT(a);(a).erase(unique((a).begin(), (a).end()), (a).end())
#define reverse(a)      reverse((a).begin(), (a).end())
#define ctos(c)         string(1, (c))
#define out(d)          cout << (d)
#define outl(d)         std::cout<<(d)<<"\n"
#define YES()           cout << "YES" << endl
#define NO()            cout << "NO" << endl
#define Yes()           cout << "Yes" << endl
#define No()            cout << "No" << endl
#define ceil(x, y)      ((x + y - 1) / (y))
#define debug(x)        cerr << #x << ": " << (x) << '\n'
#define debug2(x, y)    cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << '\n'
#define debug3(x, y, z) cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << ", " << #z << ": " << (z) << '\n'
#define dbg(v)          for (size_t _ = 0; _ < v.size(); ++_){ cerr << #v << "[" << _ << "] : " << v[_] << '\n'; }

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

const ll MOD = 1000000007; // 10^9 + 7

void solve() {
  int n; cin >> n;
  outl(int(pow(int(sqrt(n)), 2)));
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  srand((unsigned)time(NULL));
  fix(12);

  solve();
}


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

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

    const int MAX = 101;

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

        int cnt = 0;
        for (int x = 1; x <= MAX; x++) {
            if (x * x > i) continue;

            for (int y = 1; y <= MAX; y++) {
                if (x * x + y * y + x * y > i) continue;

                int b = x + y;
                int c = x * x + y * y + x * y - i;

                double rt = sqrt(b * b - 4 * c);
    // cout  << "rt: " << rt << endl;
if ((int) rt != rt) {
    // cout << rt << " " << (int) rt << endl;
    continue;
}
                ll z1 = (-b + sqrt(b * b - 4 * c)) / 2;
                ll z2 = (-b - sqrt(b * b - 4 * c)) / 2;

                if (z1 >= 1 || z2 >= 1) {
                    cnt++;
                }

            }
        }

        cout << cnt << endl;;
    }
}

Measured memory_bytes: 3668
#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>

auto& in = std::cin;
auto& out = std::cout;
#define all_range(C) std::begin(C), std::end(C)
const double PI = 3.141592653589793238462643383279502884197169399375105820974944;

int64_t A,B,C;

int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	in >> A>>B>>C;
	if (C-1 <= B ) {
		out << C + B << endl;
		return 0;
	}
	int64_t res = B*2;
	C -= B;
	out << (res + std::min(C, A+1)) << endl;

	return 0;
}
#endif


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

int main(){
  int n,k;
  cin >> n >> k;
  vector<int> a(n);
  rep(i,n) cin >> a[i];
  sort(a.begin(), a.end(), greater<int>());
  int sum = 0;
  rep(i,k) sum += a[i];
  cout << sum << endl;
  return 0;
}


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

const int N=200005;
int n,q[N],hd,tl;
long long h[N],c,dp[N];

double X(int i){return h[i];}
double Y(int i){return dp[i]+h[i]*h[i];}
double slope(int i,int j){return (Y(i)-Y(j))/(X(i)-X(j));}

int main()
{
	scanf("%d%lld",&n,&c);
	for(int i=1;i<=n;i++) scanf("%lld",&h[i]);
	q[hd=tl=1]=1;
	for(int i=2;i<=n;i++)
	{
		while(tl>hd&&slope(q[hd+1],q[hd])<2*h[i]) hd++;
		dp[i]=dp[q[hd]]+(h[i]-h[q[hd]])*(h[i]-h[q[hd]])+c;
		while(tl>hd&&slope(i,q[tl-1])<slope(q[tl],q[tl-1])) tl--;
		q[++tl]=i;
	}
	printf("%lld\n",dp[n]);
}

Measured memory_bytes: 4096
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <queue>

using ll = long long int;

int main(int argc,char *argv[])
{
	ll n;
	std::cin >> n;

	std::vector<std::string> s;
	for(ll i = 0;i < n;++i)
	{
		std::string str;
		std::cin >> str;
		s.emplace_back(str);
	}

	std::sort(s.begin(), s.end());
	
	ll ans = 1;
	ll idx = 0;
	for (ll i = 1;i < n;i++)
	{
		if (s[idx] != s[i])
		{
			idx = i;
			++ans;
		}
	}

	std::cout << ans << std::endl;

	return 0;
}

Measured memory_bytes: 11608
#include<bits/stdc++.h>
using namespace std;
const int INF=1e9+7107;
int n,k,a[100005],f[100005];
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=0;i<=n;i++) f[i]=INF;
	f[1]=0;
	for(int i=2;i<=n;i++)
	{
		for(int j=max(1,i-k);j<i;j++)
		{
			f[i]=min(f[i],f[j]+abs(a[i]-a[j]));
		}
	}
	printf("%d\n",f[n]);
	return 0;
}

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

using namespace std;

#define F first
#define S second
#define MAX_N 1e5+10
#define inf 10000000

typedef long long ll;
typedef vector<int> vi;
typedef vector<bool> vbl;

int main() {
  //freopen("input.in", "r", stdin);
  string s, t;
  cin >> s;
  cin >> t;
  int m = s.length(), n = t.length();
  int dp[m+1][n+1];
  for (int i = 0 ; i <= m ; i++) {
    for (int j = 0 ; j <= n ; j++) {
      if (i == 0 || j == 0) dp[i][j] = 0;
      else {
        if (s[i-1] == t[j-1]) {
          dp[i][j] = 1 + dp[i-1][j-1];
        }
        else {
          dp[i][j] = max(dp[i][j-1],dp[i-1][j]);
        }
      }
    }
  }

  int i = m, j = n;
  vector<char> res;
  while (i > 0 && j > 0) {
    if (s[i-1] == t[j-1]) {
      res.push_back(s[i-1]);
      i--; j--;
    }
    else {
      if (dp[i-1][j] > dp[i][j-1]) i--;
      else j--;
    }
  }

  for (int pos = res.size()-1 ; pos >= 0 ; pos--) {
    cout << res[pos];
  }

  cout << endl;

  return 0;
}

Measured memory_bytes: 35456
#include "iostream"
#include "vector"
#include "assert.h"

using namespace std;
using LL = long long;

vector< pair<LL, int>> vp;
int m;
LL n, N;

LL foo(int k, LL val) {
    if (k >= m) {
        val --;
        if (val == 0) return 0;
        if (N % val == N / val) return val;
        else return 0;
    }
    assert(k < m);
    LL rv = 0;
    rv += foo(k + 1, val);
    for (int i = 1; i <= vp[k].second; i ++) {
        val = val * vp[k].first;
        rv += foo(k + 1, val);
    }
    return rv;
}

int main() {
    cin >> n;
    N = n;
    for (LL i = 2; i * i <= n; i ++) {
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0) {
                cnt ++;
                n /= i;
            }
            vp.emplace_back(i, cnt);
        }
    }
    if (n > 1) vp.emplace_back(n, 1);
    m = vp.size();
    LL result = foo(0, 1);
    cout << result << endl;
}

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

#define ll long long
#define rep(i,n) for(int (i)=0; (i)<(n); (i)++)

const ll MOD = 1e9+7;

// Combinationの使い方
// vector<vector<ll>> v(N+1, vector<ll>(N+1, 0));
// comb(v);
void comb(vector<vector<ll>> &v){
    for(int i = 0; i < v.size(); i++){
        v[i][0] = 1;
        v[i][i] = 1;
    }
    for(int k = 1; k < v.size(); k++){
        for(int j = 1; j < k; j++){
            v[k][j] = (v[k-1][j-1] + v[k-1][j]);
            //余りを求める問題は毎回計算ごとにやる
            // v[k][j] = (v[k-1][j-1] + v[k-1][j]) % MOD;
        }
    }
}

// Union Find
struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

// vector<tuple<long,long>> items; // (value, weight)
// auto item = items[i];
// long v = get<0>(item);
// long w = get<1>(item);
// long v, w;
//   for( int i = 0; i < N; i++ ){
//     cin >> v >> w;
//     items.push_back( make_tuple(v, w) ); // item : (value, weight)
//   }

// 1 << 3 : int "3" change to bit "100"
// rep(pattern, 1 << N) if (pattern & (1 << x)) cnt++

// 過去問第3問ABC113Bまでdone

int main(){
    string s;
    cin >> s;

    for(int bit; bit < (1<<s.size()-1); bit++){
        int ans = s[0]-'0';
        string f;
        f = s[0];
        rep(i, s.size()-1){
            if(bit&(1<<i)){
                ans += s[i+1]-'0';
                f += '+';
                f += s[i+1];
            }else{
                ans -= s[i+1]-'0';
                f += '-';
                f += s[i+1];
            }
        }
        if(ans==7){
            rep(i,f.size()) cout << f[i];
            cout << '=' << ans;
            break;
        }
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

k, n = map(int, input().split())
a = [int(item) for item in input().split()]

a.append(a[0] + k)
max_diff = 0
for a1, a2 in zip(a, a[1:]):
    max_diff = max(max_diff, a2 - a1)
print(k - max_diff)

Measured memory_bytes: 24908
//                   ********** YATIN KWATRA **********

// AC BAKSHI RABBA

#include <bits/stdc++.h>
#define ll                      long long 
#define ld                      long double
#define ull                     unsigned long long 
#define FIO                     ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl                    "\n"
#define fo(i,a,b)               for(int i = a; i<=b ; i++)
#define rfo(i,a,b)              for(int i = a; i>=b ; i--)
#define vii                     vector<int>
#define vll                     vector<ll>
#define pq                      priority_queue
#define uom                     unordered_map                
#define all(v)                  v.begin(),v.end()
#define mp                      make_pair
#define pb                      push_back
#define pob                     pop_back
#define ff                      first
#define ss                      second
#define pii                     pair<int,int> 
#define pll                     pair<long,long>
#define mll                     map<ll,ll>
#define mii                     map<int,int>
#define vvii                    vector<vii>
#define vvll                    vector<vll>
#define mod                     1000000007
#define pi                      3.1415926535897932384626433832795

using namespace std;

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

/*
    
   -> Check For Overflows
   -> Out of Bounds
   -> Initialisations of global arrays and variables
   -> Its not Always Complex, Try to simplify
   -> write it down and try to solve
   -> Have Faith in urself and in ur approach
   -> If it seems totally out of reach, switch to next :)
   -> And Come Back later, if possible ..
*/


const int N = 100005;

ll dp[N];
int v[N];
int n;

void solve()
{ 
      cin >> n;

      fo(i,0,n-1) cin >> v[i];

      dp[0] = 0;
      dp[1] = abs(v[0]-v[1]);

      ll op1,op2;

      fo(i,2,n-1)
      {
         op1 = dp[i-1] + abs(v[i-1]-v[i]);
         op2 = dp[i-2] + abs(v[i-2]-v[i]);

         dp[i] = min(op1,op2);
      }       

      cout << dp[n-1] << endl;
}
int main() {
    
    FIO
    INPUT();
    
    int t;
    t = 1;
    //cin >> t;
    
    while(t--)
    {
       solve();
    }
    return 0;
}


Measured memory_bytes: 4828
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e5+5;
const int maxm=5e2+5;
const int maxq=55;
const int INF=0x3f3f3f3f;
int a[maxn],mid,n;
int s[maxn*2];
int c[maxn*2];
int lowbit(int x)
{
    return x&(-x);
}
int query(int x)
{
    int sum=0;
    while(x)
    {
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}
void add(int x)
{
    while(x<maxn*2)
    {
        c[x]++;
        x+=lowbit(x);
    }
}
int check(int mid)
{
    memset(c,0,sizeof(c));
    s[0]=0;
    for(int i=1;i<=n;i++)
    {
        s[i]=s[i-1]+(a[i]>=mid?1:-1);
    }
    ll sum=0;
    for(int i=0;i<=n;i++)
    {
        sum+=query(s[i]+maxn);
        add(s[i]+maxn);
    }
    return sum*2>=1ll*n*(n+1)/2;
}
int main()
{
    while(~scanf("%d",&n))
    {
        int l=0;int r=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            r=max(r,a[i]);
        }
        int ans=0;
        while(l<=r)
        {
            mid=(l+r)/2;
            if(check(mid))
            {
                ans=mid;
                l=mid+1;
            }
            else r=mid-1;
        }
        printf("%d\n",ans);
    }
}


Measured memory_bytes: 1792
n=int(input())
dp=[float("inf")]*(n+1)
dp[0]=0
for i in range(n):
    for j in range(1,7):
        j=6**j
        if i+j<n+1:
            dp[i+j]=min(dp[i+j],dp[i]+1)
    for j in range(1,6):
        j=9**j
        if i+j<n+1:
            dp[i+j]=min(dp[i+j],dp[i]+1)
    dp[i+1]=min(dp[i+1],dp[i]+1)
print(dp[-1])

Measured memory_bytes: 48208
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();
        int[] x = new int[n];
        for (int i = 0 ; i < n ; i++) {
            x[i] = sc.nextInt();
        }
        long ans = 0;
        for (int i = 0 ; i < n - 1 ; i++) {
            ans += (long) Math.min(b,(long) (x[i + 1] - x[i]) * a);
        }

        System.out.println(ans);

    }

}

Measured memory_bytes: 51112
xy = list(map(int,input().split()))

if xy[2] - xy[0] == 0:
    if xy[3] > xy[1]:
        x3 = xy[2] - (xy[3]-xy[1])
        y3 = xy[3] - (xy[0]-xy[2])
        x4 = xy[0] - (xy[3]-xy[1])
        y4 = xy[1] - (xy[2]-xy[0])
    else:
        x3 = xy[2] - (xy[3]-xy[1])
        y3 = xy[3] - (xy[0]-xy[2])
        x4 = xy[0] - (xy[3]-xy[1])
        y4 = xy[1] - (xy[0]-xy[2])
else:
    if xy[2] > xy[0]:
        x3 = xy[2] - (xy[3]-xy[1])
        y3 = xy[3] - (xy[0]-xy[2])
        x4 = xy[0] - (xy[3]-xy[1])
        y4 = xy[1] - (xy[0]-xy[2])
    else:
        x3 = xy[2] - (xy[3]-xy[1])
        y3 = xy[3] - (xy[0]-xy[2])
        x4 = xy[0] - (xy[3]-xy[1])
        y4 = xy[1] - (xy[0]-xy[2])

print(x3,y3,x4,y4)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
/* ------------------------------------------------ */
ll fact(int i) {       //階乗
    if (i == 0) return 1;
    return (fact(i - 1)) * i;
}
ll gcd(ll a, ll b) {        //最大公約数
    if(b == 0) return a;
    return gcd(b, a % b); 
}
ll lcm(ll a, ll b) {      //最小公倍数
    return a * b / gcd(a, b);
}
int keta(ll n) {        //桁数を求める
    if(n == 0) return 1;
    int count = 0;
    while(n != 0) {
        n /= 10;
        count++;
    }
    return count;
}
ll ketasum(ll n) {    //各桁の和
    ll sum = 0;
    while(n != 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
/* ------------------------------------------------ */

int main() {
    int n;
    cin >> n;
    vector<ll> a(n), b(n);
    rep(i, n) cin >> a[i] >> b[i];
    ll ans = 0;
    for(int i = n - 1; i >= 0; --i) {
        a[i] += ans;
        if(a[i] % b[i] == 0) continue;
        ans += b[i] - (a[i] % b[i]);
        // cout << b[i] - (a[i] % b[i]) << endl;
    }
    cout << ans << endl;
}

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

int main()
{
    int N;
    cin >> N;
    int pi;
    int c = 0;
    for(int i=0;i<N;i++){
        cin >> pi;
        if(pi!=i+1) c++;
    }
    if(c<=2) cout<<"YES"<<endl;
    else     cout<<"NO"<<endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  
  string S;
  cin >> S;
  
  bool flag=0;
  if(S[0]==S[1] && S[2]==S[3] && S[1]!=S[2]) flag=!flag;
  else if(S[0]==S[3] && S[1]==S[2] && S[0]!=S[1]) flag=!flag;
  else if(S[0]==S[2] && S[1]==S[3] && S[0]!=S[1]) flag=!flag;
  
  if (flag) cout << "Yes" << endl;
  else cout << "No" << endl;
	
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(b) - 1;i>=(a);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)

#define PB push_back
#define INF (1<<29)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define CLR(a) memset(a,0,sizeof(a))
const int dx[] = {-1,0,0,1},dy[] = {0,1,-1,0};

typedef long long int ll;

using namespace std;

int main(){
    while(true){
	int m;
	cin >> m;
	if(m==0) break;
	REP(i,9) {
	    int temp;
	    cin >> temp;
	    m -= temp;
	}
	cout << m << endl;
    }
    return 0;
}

Measured memory_bytes: 1160
#include<stdio.h>

void swap(int *a,int *b){
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

int bubbleSort(int *A,int N){
    int i,j;//i?????´?????????????????°
    int count=0;
    for(i=0;i<N;i++){
        for(j=N-1;j>i;j--){
            if(A[j]<A[j-1]){
                swap(&A[j],&A[j-1]);
                count++;
            }
        }
    }
    return count; 
}

int main(){
    int A[100];
    int i,N,count;
    scanf("%d",&N);
    for(i=0;i<N;i++){
        scanf("%d",&A[i]);
    }
    count = bubbleSort(A,N);
    for(i=0;i<N;i++){
        if(i==0){
            printf("%d",A[i]);
        }else{
            printf(" %d",A[i]);
        }
    }
    printf("\n%d\n",count);
    return 0;
}

Measured memory_bytes: 1848