akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define LOOP(n) for (int _i = 0; _i < (n); _i++)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define FOR(i, r, n) for (int i = (r); i < (n); ++i)
#define ALL(obj) begin(obj), end(obj)
using namespace std;
using ll = long long;
using ull = unsigned long long;

bool abs_chmin(ll &a, ll &b) {
    if (abs(a) > abs(b)) {
        b = a;
        return 1;
    };
    return 0;
}
bool abs_chmax(ll &a, ll &b) {
    if (abs(a) < abs(b)) {
        b = a;
        return 1;
    };
    return 0;
}

int N, K;
ll dp[3005][3005];
int main() {
    // cin.tie(0);
    // ios::sync_with_stdio(false);

    cin >> N;
    vector<int> A(N + 1);
    REP(i, N) cin >> A.at(i + 1);

    FOR(s, 2, N + 2) {
        FOR(j, s, N + 2) {
            int i = j - s + 1;
            if ((N - (j - i)) % 2 == 0) {  // 太郎
                dp[i][j] = max(dp[i][j - 1] + A[j - 1], dp[i + 1][j] + A[i]);
            } else {  // 次郎
                dp[i][j] = min(dp[i][j - 1] - A[j - 1], dp[i + 1][j] - A[i]);
            }
        }
    }

    cout << dp[1][N + 1] << endl;

    return 0;
}


Measured memory_bytes: 70016
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 3000

enum DIR{
	North,
	East,
	South,
	West,
};

struct Info{
	int x,y;
	DIR dir;
};

typedef pair<int,int> Data;
int N;
map<int,int> X_MAP,Y_MAP;
vector<int> Y,X;
Info info[NUM];
set<Data> SET_X[NUM],SET_Y[NUM];

int main(){

	scanf("%d",&N);

	char buf[2];

	for(int i = 0; i < N; i++){
		scanf("%d %d %s",&info[i].x,&info[i].y,buf);
		X.push_back(info[i].x);
		Y.push_back(info[i].y);
		switch(buf[0]){
		case '^':
			info[i].dir = North;
			break;
		case '>':
			info[i].dir = East;
			break;
		case 'v':
			info[i].dir = South;
			break;
		case '<':
			info[i].dir = West;
			break;
		}
	}

	sort(X.begin(),X.end());
	sort(Y.begin(),Y.end());

	X.erase(unique(X.begin(),X.end()),X.end());
	Y.erase(unique(Y.begin(),Y.end()),Y.end());

	for(int i = 0; i < X.size(); i++){
		X_MAP[X[i]] = i;
	}
	for(int i = 0; i < Y.size(); i++){
		Y_MAP[Y[i]] = i;
	}

	int size_X = (int)X.size(),size_Y = (int)Y.size();

	for(int i = 0; i < N; i++){
		info[i].y = Y_MAP[info[i].y];
		info[i].x = X_MAP[info[i].x];
	}

	int ans = 0;
	int x,y,next_index;
	DIR dir;
	Data tmp;
	bool FLG;

	for(int start = 0; start < N; start++){

		for(int i = 0; i < NUM; i++){
			SET_X[i].clear();
			SET_Y[i].clear();
		}

		int tmp_count = 1;

		for(int i = 0; i < N; i++){
			if(i == start)continue;
			SET_X[info[i].x].insert(Data(info[i].y,i));
			SET_Y[info[i].y].insert(Data(info[i].x,i));
		}

		dir = info[start].dir;
		x = info[start].x;
		y = info[start].y;

		FLG = true;

		set<Data>::iterator it;

		while(true){

			switch(dir){
			case North:
				it = SET_X[x].lower_bound(Data(y,0));
				if(it == SET_X[x].begin()){
					FLG = false;
				}else{
					it--;
					tmp = *it;
					next_index = tmp.second;
				}
				break;
			case East:
				it = SET_Y[y].lower_bound(Data(x,0));
				if(it == SET_Y[y].end()){
					FLG = false;
				}else{
					tmp = *it;
					next_index = tmp.second;
				}
				break;
			case South:
				it = SET_X[x].lower_bound(Data(y,0));
				if(it == SET_X[x].end()){
					FLG = false;
				}else{
					tmp = *it;
					next_index = tmp.second;
				}
				break;
			case West:
				it = SET_Y[y].lower_bound(Data(x,0));
				if(it == SET_Y[y].begin()){
					FLG = false;
				}else{
					it--;
					tmp = *it;
					next_index = tmp.second;
				}
				break;
			}

			if(!FLG)break;

			tmp_count++;
			x = info[next_index].x;
			y = info[next_index].y;
			dir = info[next_index].dir;
			SET_X[x].erase(Data(y,next_index));
			SET_Y[y].erase(Data(x,next_index));
		}
		ans = max(ans,tmp_count);
	}

	printf("%d\n",ans);

	return 0;
}





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

int main(){
  int t[10005];
  
  t[0]=1;
  for(int i=1;i<=10000;i++){
    t[i]=t[i-1]+i;
  }
  int n;
  while(cin>>n){
    cout<<t[n]<<endl;
  }
  return 0;
}



Measured memory_bytes: 3116
#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 all(a)          (a).begin(), (a).end()
#define sort(a)         sort(all(a))
#define uniq(a)         sort(a);(a).erase(unique(all(a), (a).end())
#define reverse(a)      reverse(all(a))
#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'; }
#define pb              push_back
#define fst             first
#define int             long long

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

const ll MOD = 1000000007; // 10^9 + 7
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

void solve() {
  ll N; cin >> N;
  const int MAX = 3500;
  for (int h = 1; h <= MAX; h++) {
    for (int n = h; n <= MAX && 4*h*n/(h+n) > N; n++) {
      if (N * h * n % (4 * h * n - N * (n + h)) == 0) {
        int w = N * h * n / (4 * h * n - N * (n + h));
        cout << h << " " << n << " " << w << endl;
        return;
      }
    }
  }
}

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

  solve();
}


Measured memory_bytes: 256
n,k = gets.split.map(&:to_i)
r,s,p = gets.split.map(&:to_i)
score = Array.new(n){[]*3}
R,S,P = 0,1,2

gets.chomp.split("").each_with_index do |t,i|
  sr, ss, sp = 0,0,0
  sr = r if t == "s"
  ss = s if t == "p"
  sp = p if t == "r"
  if i-k >= 0
    sr = 0 if score[i-k][R] != 0
    ss = 0 if score[i-k][S] != 0
    sp = 0 if score[i-k][P] != 0
  end
  score[i][R] = sr
  score[i][S] = ss
  score[i][P] = sp
end
ans = 0
score.each {|s| ans += s.max}
p ans


Measured memory_bytes: 30120
/*
 * atcoder/abc114/c.cpp
 */

// C++ 14
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring> // memset
#include <cassert>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
template <class T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template <class T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }

string S;
int N;

/*
 * 10 * 2 * 2 * 2 * 2 * 2 * 10 = 3200
 */
ll rec(int n = 0, int acc = 0, bool zero = true, bool three = false, bool five = false, bool seven = false, bool l = true) {
  if (n==N) {
    // cout << acc << " " << (three and five and seven) << endl;
    return three and five and seven;
  }
  int u = l ? S[n] - '0' : 9;

  ll ways = 0;
  for (int d=0; d<=u; d++) {
    if (!zero and d == 0) continue; // 先頭から連続した0のみ許可
    if (d == 0 or d == 3 or d == 5 or d == 7) {
      ways += rec(n+1, acc*10+d, zero and d == 0, three or (d == 3), five or (d == 5), seven or (d == 7), l and d == u);
    }
  }
  return ways;
}

void solve() {
  cin >> S;
  N = S.size();
  cout << rec() << endl;
}
int main() {
  // cout.precision(15);
  // cout << fixed << double

  solve();

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ALL(v) v.begin(),v.end()
#define UN(v) sort(ALL(v)),v.erase(unique(ALL(v)))
#define FILL(x,y) memset(x,y,sizeof(x))
#define EACH(v,it) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define FIO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef unsigned int uint;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
const string M="Male",F="Female",N="Vacant";
int n;
map<int,int> mp;
/*---main code---*/ 

int get(int x)
{
	if(mp.find(x)!=mp.end())
	{
		return mp[x];
	}
	printf("%d\n",x);
	fflush(stdout);
	string s;
	cin>>s;
	if(s==N)
	{
		exit(0);
	}
	mp[x]=(s==M);
	return mp[x];
}

int main()
{
	FIO;
	cin>>n;
	int s=get(0),t=s;
	int L=0,R=n;
	while(1)
	{
		int mid=(L+R)>>1;
		int ms=get(mid);
		if(mid%2==L%2)
		{
			if(ms==s)
			{
				L=mid,s=ms;
			}
			else
			{
				R=mid,t=ms;
			}
		}
		else
		{
			if(ms!=s)
			{
				L=mid,s=ms;
			}
			else
			{
				R=mid,t=ms;
			}
		}
	}
	return 0;
}


Measured memory_bytes: 852
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;

/*2進数配列+1*/
vector<int> twoadd(vector<int> v, int N){
    v[N-1]+=1;
    int ind = N-1;
    int j=N-1;
    for(j=N-1;j>=1;j--){
        if(v[j]>1){
            v[j-1]+=1;
            v[j]=0;
        }
    }
    return v;
}

/*フィボナッチ*/
long long fibonatti(long long d){
    long long count = 0;
    long long f1 = 1;
    long long f2 = 1;/*ここを変える*/
    long long temp;
    if(d == 1){
        count = f1;
    }else if(d == 2){
        count = f2;
    }else if(d==0){
        count = 1;
    }else{
        for(int i=0;i<d-2;i++){
            temp = f1+f2;
            f1 = f2;
            f2 = temp;
        }
        count = temp;
    }
    return count;
}

/*最大公約数*/
unsigned long long GCD(long long L,long long R){
    if(L>R){
        long long temp=R;
        R = L;
        L = temp;
    }
    unsigned long long pp=0,ppt=0;
    unsigned long long ans=0;
    if(R%L==0){
        ans = L;
    }else{
        while(true){
            ppt = pp;
            pp=R%L;
            if(pp == 0){
                ans = ppt;
                break;
            }
            R = L;
            L = pp;
        }
    }    
    return ans;    
}

/*最小公倍数*/
unsigned long long LCM(long long L,long long R){
    unsigned long long ans;
    unsigned long long gcd = GCD(L,R);
    ans = (L/gcd)*R;
    return ans;
}

/*Combination set*/
#define mod 1000000007
#define maxcomb 3000/*大きいものを求めるときはここを変える*/
vector<long long> fc(maxcomb+1);
vector<long long> ifc(maxcomb+1);
long long modpow(long long x,long long n){
    long long ans = 1;
    while(n > 0){
        if(n & 1) {
            ans = ans*x%mod;
        }
        x = x*x%mod;
        n >>= 1;
    }
    return ans;
}
void Conb(){
    fc[0]= 1;
    ifc[0]=1;
    for(long long i=0;i<maxcomb;i++){
        fc[i+1] = fc[i]*(i+1)%mod;//n!(mod)
        ifc[i+1] = ifc[i]*modpow(i+1,mod-2)%mod;//k!^{M-2} (mod)
    }
}
unsigned long long Combination(long long L,long long R){
    unsigned long long up=1,ans;
    Conb();
    if(L==0&&R==0){
        return 1;
    }else if(L<R||L<0){
        return 0;
    }else{
        long long t = ifc[L-R]*ifc[R]%mod;
        ans = t*fc[L]%mod;
    }
    return ans;
}
/*Combination set ここまで*/

/*ここから*/
int main() {
    int N, D;
    cin >> N >> D;
    int ans = N/(D*2+1);
    if(N%(D*2+1)!=0){
        ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3700
#include<iostream>
#include<string>
#include<math.h>
using namespace std;

int main(){
    double b;
    cin>>b;

    double a[100000];
    double sum=0;
    for(int i=0;i<b;++i){
        cin>>a[i];
        sum+=a[i];
    }
    double avg = sum/b; 

    double avgmin = 101,Min;
    for(int i=0;i<b;++i){
        if(fabs(avg-a[i]) < avgmin){
            avgmin = fabs(avg-a[i]);
            Min = i;
        }
    }
    cout<<Min;
    /*for(int i=0;i<b;++i){
        cout<<a[i]<<" ";
    }
    cout<<sum;*/

}

Measured memory_bytes: 256
object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val n = sc.nextInt
  var a = new Array[Int](n + 2)
  a(0) = 0
  a(n + 1) = 0
  for (i <- 1 until n + 1) {
    a(i) = sc.nextInt()
  }
  val accL = new Array[Int](n + 2)
  for (i <- 1 until n + 2) {
    accL(i) = accL(i - 1) + math.abs(a(i) - a(i - 1))
  }
  var accR = new Array[Int](n + 2)
  val reverseA = a.reverse
  for (i <- 1 until n + 2) {
    accR(i) = accR(i - 1) + math.abs(reverseA(i) - reverseA(i - 1))
  }
  accR = accR.reverse

  //indexやら、reverseやら全然整理がつかん。。
  val pw = new java.io.PrintWriter(System.out)
  for (i <- 1 until n + 1) {
    val cost = accL(i - 1) + math.abs(a(i - 1) - a(i + 1)) + accR(i + 1)
    pw.println(cost)

  }
  pw.flush()

}


Measured memory_bytes: 59864
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
#define INF 1007654321
#define PI 3.14159265358979
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repp(i, s, e) for(int i = (s); i <= (e); ++i)
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
#define FAST_IO() ios::sync_with_stdio(0); cin.tie(0)
template<typename T>
ostream& operator<<(ostream &os, const vector<T> &v) { for (auto x : v) os << x << " "; return os << "\n"; }
template<typename U, typename V>
ostream& operator<<(ostream &os, const pair<U, V> &p) { return os << "(" << p.first << "," << p.second << ")";}

const ll MOD = 1e9 + 7;

int main() {
    FAST_IO();
    int N, M; cin >> N >> M;
    int S, T; cin >> S >> T;
    vector<vector<pll>> adj(N);
    --S, --T;
    rep(i, M) {
        ll u, v, d; cin >> u >> v >> d;
        adj[u-1].push_back({v-1, 2*d});
        adj[v-1].push_back({u-1, 2*d});
    }
    // Dijkstra on S
    vector<ll> dist(N, LONG_MAX);
    priority_queue<pll, vector<pll>, greater<pll>> pq;
    dist[S] = 0;
    pq.push({dist[S], S});
    while(!pq.empty()) {
        ll here = pq.top().second;
        ll d = pq.top().first; pq.pop();
        if(dist[here] < d) continue;
        for(auto &e : adj[here]) {
            ll &next = e.first;
            if(dist[next] > dist[here] + e.second) {
                dist[next] = dist[here] + e.second;
                pq.push({dist[next], next});
            }
        }
    }
    ll D = dist[T] / 2;
    vector<pii> B;
    rep(u, N) {
        if(dist[u] == D) {
            B.push_back({u, u});
        } else {
            for(auto &e : adj[u]) {
                ll &v = e.first;
                if(dist[u] + e.second == dist[v] && dist[u] < D && dist[v] > D) {
                    B.push_back({u, v});
                }
            }
        }
    }
    // calculate cnt(S, u), cnt(v, T)
    vector<ll> cntS(N), cntT(N);
    cntS[S] = 1; cntT[T] = 1;
    vector<pll> sorted(N);
    rep(i, N) sorted[i] = {dist[i], i};
    sort(all(sorted));
    rep(i, N) {
        int j = sorted[i].second;
        for(auto &e : adj[j]) {
            if(dist[j] + e.second == dist[e.first]) {
                cntS[e.first] = (cntS[e.first] + cntS[j]) % MOD;    
            }
        }
    }
    rep(i, N) {
        int j = sorted[N - 1 - i].second;
        for(auto &e : adj[j]) {
            if(dist[j] - e.second == dist[e.first]) {
                cntT[e.first] = (cntT[e.first] + cntT[j]) % MOD;
            }
        }
    }
    ll sum = 0, sq_sum = 0;
    for(auto &p : B) {
        ll Y = (cntS[p.first] * cntT[p.second]) % MOD;
        sum = (sum + Y) % MOD;
        sq_sum = (sq_sum + Y*Y%MOD) % MOD;
    }
    cout << (sum*sum%MOD - sq_sum + MOD) % MOD << "\n";
}


Measured memory_bytes: 18544
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
using namespace std;
int main() {
  int n,a[100000],cnt=0;
  cin >> n;
  for(int i=0; i<n; i++) {
    cin >> a[i];
    if(a[i]%2!=0) {
      cnt++;
    }
  }
  if(cnt%2==0) {
    cout << "YES" << endl;
  }
  else {
    cout << "NO" << endl;
  }
}

Measured memory_bytes: 640
n,m=map(int,input().split())
ac={}
wa=[0]*n
a=0
w=0
for i in range(n):
    ac[i+1]=0
    
for i in range(m):
    l=input().split()
    if ac[int(l[0])]!='AC':
        if l[1]=='AC':
            ac[int(l[0])]='AC'
            a+=1
            w+=wa[int(l[0])-1]
        else:
            wa[int(l[0])-1]+=1
    if a==n:
        break
print(a,w)


Measured memory_bytes: 15852
fun main() {
    var (a, b, c, k) = readLine()!!.split(" ").map(String::toLong)

    var n = 0L
    if (a > k) {
        println(k)
        return
    } else {
        n += a
        k -= a
    }

    if (b > k) {
        println(n)
        return
    } else {
        k -= b
    }

    n -= k

    println(n)
}





Measured memory_bytes: 36452
str_ary = gets.chomp.split("")
count = Hash.new(0)
str_ary.each do |elem|
    count[elem] += 1
end

ans = 0
count.each do |k, v| #１つでも偶数じゃないやつが見つかったらアウト
    if v % 2 ==1
        ans += 1
        break
    end
end

if ans == 0
    puts "Yes"
else
    puts "No"
end

Measured memory_bytes: 1788
#include <bits/stdc++.h>
#ifdef __DEBUG__
    #define DBG(X) cout << #X << " = " << (X) << endl;
    #define SAY(X) cout << (X) << endl;
#else
    #define DBG(X)
    #define SAY(X)
#endif

using namespace std;

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

int dx[]={1, 0, -1, 0, 1,-1, 1,-1};
int dy[]={0, 1, 0, -1, 1, 1,-1,-1};
const int INT_INF = (int)(2e9);
const ll  LL_INF = (ll)(2e18);

inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); };
template<typename T, typename S> inline ostream& operator<<(ostream& os, const pair<T, S> p) { cout << "[" << p.first << ";" << p.second << "]"; return os; }
template<typename T, typename S> inline ostream& operator<<(ostream& os, const map<T, S> p) { for (auto el : p) cout << "[" << el.first << ";" << el.second << "]"; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) { for (auto el : v) cout << el << " "; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const deque<T>& v) { for (auto el : v) cout << el << " "; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const set<T>& v) { for (auto el : v) cout << el << " "; return os; }
template<typename T> inline vector<T> fetch_vec(int sz) { vector<T> ret(sz); for (auto& elem : ret) cin >> elem; return ret; }

int N;
vector<ll> L;
void input(){
    fast_io();
    cin >> N;
    L = fetch_vec<ll>(N);
}

int solve(){
    sort(L.begin(),L.end());
    ll ans = 0;
    for (int i = 0; i < N; i++)
    {
        for (int j = i+1; j < N; j++)
        {
            for (int k = j+1; k < N; k++)
            {
                if(L[i]!=L[j] && L[j]!=L[k]){
                    if(L[i]+L[j]>L[k]) ans++;
                }
            }
        }
    }
    cout << ans << endl;    
    return 0;
}   

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

Measured memory_bytes: 3660
#include<bits/stdc++.h>
using namespace std;
long long M=998244353;
void solve(){
	int n,l,p,q;
	cin>>n>>l;
	vector<pair<int,int>>X(l,{0,0});
	for(int i=0;i<l;i++) cin>>X[i].first>>X[i].second;
	sort(X.begin(),X.end());
	vector<pair<int,int>>A;
	A.push_back(X[0]);
	for(int i=1;i<l;i++){
		if(X[i].first<=A.back().second) A.back().second=max(X[i].second,A.back().second);
		else A.push_back(X[i]);
	}
	vector<long long>dp(n+1);
	vector<long long>sum(n+1);
	dp[1]=1;
	sum[1]=1;
	for(int i=2;i<=n;i++){
		for(auto a:A){
			if(a.first>=i) break;
			int t=max(i-a.second-1,0);
			dp[i]=(dp[i]+sum[i-a.first]-sum[t]+M)%M;
		}
		sum[i]=(sum[i-1]+dp[i])%M;
		// cout<<i<<" "<<dp[i]<<" "<<sum[i]<<"\n";
	}
	cout<<dp[n];
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	solve();

}

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

#define fast_io() ios::sync_with_stdio(false); cin.tie(nullptr)
#define ll long long int

int main(){
    fast_io();

    int N,M; //件数, 遅延日数
    cin >> N >> M;

    int A[N],B[N];

    ll ans = 0;
    int ind=0;

    vector<pair<int,int>> v; //遅延日数, 報酬

    for (int i = 0; i < N; i++) {
      cin >> A[i] >> B[i];
      v.push_back(make_pair(A[i], B[i]));
    }

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

    priority_queue<int> q;

    int index = 0;
    for( int i = 0; i < M; i++) {
      while (i+1 == v[index].first && index < v.size()) {
        q.push(v[index].second);
        index++;
      }

      if(!q.empty()) {
        int buf = q.top();
        q.pop();
        ans += buf;
      }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 5536
n, k = gets.split.map(&:to_i)
R, S, P = gets.split.map(&:to_i)
table = {"s" => R, "p" => S, "r" => P}
win_pattern = {"s" => "r", "p" => "s", "r" => "p"}
t = gets.chomp.split("")
score = 0
hands = []
 
n.times do |i|
    if i > k - 1
        if win_pattern[t[i]] == hands[i - k]
            hands.push(["r", "s", "p"].reject { |h| h == hands[i - k] || h == win_pattern[t[i + k]] }.first)
            next
        end
    end
    
    score += table[t[i]]
    hands.push(win_pattern[t[i]])
end
 
p score

Measured memory_bytes: 13564
import java.util.*;
import java.io.InputStreamReader;
import java.io.BufferedReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        String[] a = br.readLine().split(" ");
        String[] b = br.readLine().split(" ");
        String[] c = br.readLine().split(" ");
        Integer[] A = new Integer[n];
        Integer[] B = new Integer[n];
        Integer[] C = new Integer[n];
        
        for (int i = 0; i < n; i++) {
            A[i] = Integer.parseInt(a[i]);
            B[i] = Integer.parseInt(b[i]);
            C[i] = Integer.parseInt(c[i]);
        }
        
        Arrays.sort(A);
        Arrays.sort(C);
        
        long ans = 0;
        for (int i = 0; i < n; i++) {
            int ab = ~Arrays.binarySearch(A, B[i], (x,y)->x.compareTo(y)>=0?1:-1);
            int bc = n - ~Arrays.binarySearch(C, B[i], (x,y)->x.compareTo(y)>0?1:-1);
            
            ans += (long)ab*bc;
        }
        
        System.out.println(ans);
    }
}





Measured memory_bytes: 66128
n = int(input())
h = list(map(int, input().split()))


def mizuyari(partial_list):
    count = 0
    # print(partial_list)
    if len(partial_list) == 0:
        # print('end return------------ 0 ')
        return 0
    if len(partial_list) == 1:
        # print('end return------' + str(partial_list[0]))
        return partial_list[0]
    # リストに0がない場合は，どれかが0になるまでリストの各要素の数値を減らす
    if min(partial_list) != 0:
        count += min(partial_list)
        # print('count --------' + str(min(partial_list)))
        partial_list = list(map(lambda x: x-min(partial_list), partial_list))
    zero_index = []
    # 分割
    for i in range(len(partial_list)):
        if partial_list[i] == 0:
            zero_index.append(i)
    # print(zero_index)
    bunkatsu = []
    bunkatsu.append(partial_list[0:zero_index[0]])
    for i in range(0, len(zero_index)-1):
        bunkatsu.append(partial_list[zero_index[i]+1:zero_index[i+1]])
    bunkatsu.append(partial_list[zero_index[(len(zero_index)-1)]+1:len(partial_list)])
    # print(bunkatsu)
    for i in bunkatsu:
        count += mizuyari(i)
    return count


print(mizuyari(h))


Measured memory_bytes: 3188
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#define gI gi
#define itn int
#define File(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)

using namespace std;

typedef long long ll;

inline ll gi()
{
    ll f = 1, x = 0; char c = getchar();
    while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
    while (c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}
    return f * x;
}

const ll INF = 2000000007;

ll n, m, lmax, lmin = INF, rmax, rmin = INF, ans, sum, minn[200003], maxx[200003];
ll ans1, ans2;
struct Node
{
	ll x, y;
} a[200003];

inline bool cmp(Node xx, Node yy)
{
	if (xx.x != yy.x) return xx.x < yy.x;
	return xx.y < yy.y;
}

int main()
{
	//File("D");
	n = gi();
	for (ll i = 1; i <= n; i+=1)
	{
		a[i].x = gi(), a[i].y = gi();
		if (a[i].x > a[i].y) swap(a[i].x, a[i].y);
		lmin = min(lmin, a[i].y), lmax = max(lmax, a[i].y);
		rmin = min(rmin, a[i].x), rmax = max(rmax, a[i].x);
	}
	ans1 = (lmax - lmin) * (rmax - rmin);
	lmin = rmin;
	sort(a + 1, a + 1 + n, cmp);
	minn[1] = maxx[1] = a[1].y;
	ans2 = INF;
	for (ll i = 2; i <= n; i+=1)
	{
		minn[i] = min(minn[i - 1], a[i].y);
		maxx[i] = max(maxx[i - 1], a[i].y);
		if (i != n) ans2 = min(ans2, max(maxx[i], a[n].x) - min(minn[i], a[i + 1].x));
	}
	ans2 = ans2 * (lmax - lmin);
	printf("%lld\n", min(ans2, ans1));
	return 0;
}


Measured memory_bytes: 6528
N = int(input())

prime = [0] * 101

for i in range(2, N + 1):
    temp = i

    for j in range(2, N + 1):
        while temp % j == 0:
            prime[j] += 1
            temp //= j

        if temp == 1:
            break

ans = 0

for i in range(2, N + 1):
    temp1 = prime[i]

    if temp1 == 0:
        continue
    
    if temp1 >= 74:
        ans += 1
    
    for j in range(i + 1, N + 1):
        temp2 = prime[j]

        if temp2 == 0:
            continue
        
        temp_list = [temp1, temp2]

        order1 = [0, 1]
        order2 = [1, 0]

        for h in range(2):
            if temp_list[order1[h]] >= 4 and temp_list[order2[h]] >= 14:
                ans += 1

            if temp_list[order1[h]] >= 2 and temp_list[order2[h]] >= 24:
                ans += 1
        
        for k in range(j + 1, N + 1):
            temp3 = prime[k]

            if temp3 == 0:
                continue
            
            temp_list = [temp1, temp2, temp3]

            order1 = [0, 1, 2]
            order2 = [1, 2, 0]
            order3 = [2, 0, 1]

            for h in range(3):
                if temp_list[order1[h]] >= 2 and temp_list[order2[h]] >= 4 and temp_list[order3[h]] >= 4:
                    ans += 1

print(ans)


Measured memory_bytes: 3064
N = int(input())
K = int(input())
L = len(str(N))
dp1 = [[0 for _ in range(K+1)] for _ in range(L+1)]
dp2 = [[0 for _ in range(K+1)] for _ in range(L+1)]
count = 0
for i in range(L+1):
    dp1[i][0] = 0
count = 0
for i, c in enumerate(str(N)):
    c = int(c)
    if i == 0:
        dp1[i+1][0] = 1
        dp1[i+1][1] = c-1
        dp2[i+1][1] = 1
        count = 1
        continue

    for j in range(0, K+1):
        if c == 0:
            dp2[i+1][j] += dp2[i][j]
        else:
            if j != K:
                dp2[i+1][j+1] += dp2[i][j]
    for j in range(0, K+1):
        if c != 0:
            dp1[i+1][j] += dp2[i][j]
        dp1[i+1][j] += dp1[i][j]


        if j != K:
            if count >= K:
                dp1[i+1][j+1] += dp2[i][j] * 9
                dp1[i+1][j+1] += dp1[i][j] * 9
            else:
                dp1[i+1][j+1] += dp2[i][j]*max(0, (c-1))
                dp1[i+1][j+1] += dp1[i][j]*9
    #print(dp1)
    #print(dp2)
print(dp1[-1][-1] + dp2[-1][-1])



Measured memory_bytes: 38464
#include<iostream>
#include<string>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<deque>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<iomanip>
#include<sstream>
using namespace std;

#define pi acos(-1.0)
#define ms(x,n) memset(x,n,sizeof(x));
#define pb push_back

typedef long long ll;//string::npos
typedef long long iint;

ll gcd(ll a,ll b) {
	return a%b==0?b:gcd(b,a%b);
}
ll lcm(ll x,ll y) {
	ll z=gcd(x,y);
	return x*y/z;
}

const int MAXX=2e5+5;
const int INF=1e7+5;
const int mod=998244353;

//vector<int> vt;
//pair<int,int> p;
//map<int,int> m;
int a[2000];
int main() {
	ios::sync_with_stdio(false);
	
	long long a,b;
	cin>>a>>b;
	cout<<min(a%b,b-a%b)<<endl;
	
}



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

int main() {
	string s;
	cin >> s;
	string keyence = "keyence";
	int i = 0;
	while (keyence[i] == s[i]) {
		i++;
		if (i == 7) {
			cout << "YES" << endl;
			return 0;
		}
	}
	while (keyence[i] == s[s.length() - 7 + i]) {
		i++;
		if (i == 7) {
			cout << "YES" << endl;
			return 0;
		}
	}
	cout << "NO" << endl;
	return 0;
}

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

signed main(){
  int A,B;
  cin>>A>>B;
  if(A+B>=10){
    cout<<"error";
    return 0;
  }
  cout<<A+B<<endl;
  return 0;
}

Measured memory_bytes: 3564
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <map>

std::string s;
int ans;

int judge(int x, int y)
{
	for (int i = x; i <= y; ++i)
		if (s[i] != 'A' && s[i] != 'T' && s[i] != 'C' && s[i] != 'G')
			return 0;
	return 1;
}

int main()
{
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	std::cin >> s;
	for (int i = 0; i < s.size(); ++i)
		for (int j = i; j < s.size(); ++j)
			if (judge(i, j))
				ans = std::max(ans, j - i + 1);
	std::cout << ans << "\n";
	return 0;
}

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

#define debug(x) cerr<<#x<<"="<<x<<endl;
#define m(a,b) memset(a,b,sizeof(a))
typedef long long ll;

int main(){
	int a,b;
	cin>>a>>b;
	if (a*b%2==0) printf("Even\n");
	else printf("Odd\n");
	return 0;
}

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

int main() {
  string S;
  cin >> S;
  bool flag = false;
  for (int i = 0; i < S.size(); i += 2)
    if (S[i] == 'L')
      flag = true;
  for (int i = 1; i < S.size(); i += 2)
    if (S[i] == 'R')
      flag = true;
  if (!flag)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

Measured memory_bytes: 256
//cf.cpp
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <string.h>
#include <cstring>
#include <queue>
#include <math.h>
#include <stack>
#include <bitset>
#include <utility>
#define mp make_pair
#define pb push_back
#define llc (long long)
#define pob pop_back
#define pm %1000000007
using namespace std;

bool comp(long long x, long long y){
	return x>y;
}
int main(){
	int n, k;
	long long inp;
	long long ps[1000];
	vector <long long> sums;
	cin>>n>>k;
	long long ans=0;
	cin>>ps[0];sums.pb(ps[0]);
	for(int i = 1;i < n;i ++){
		cin>>inp;
		ps[i]=ps[i-1]+inp;
		sums.push_back(ps[i]);
	}
	for(int i = 1;i < n;i ++){
		for(int j = 0;j < i;j ++){
			sums.pb(ps[i]-ps[j]);
		}
	}
	sort(sums.begin(),sums.end(),comp);
	for(int i = 39;i >= 0;i --){
		if(sums[0]&(1ll<<i)){
			if(sums[0]&sums[k-1]&(1ll<<i)){
				ans+=1ll<<i;
				for(int j = k;j < sums.size();j ++){
					if(sums[j]&(1ll<<i))continue;
					sums.resize(j);
				}
			}else{
				for(int j = 0;j < k;j ++){
					if(sums[j]&(1ll<<i)){
						sums[j]-=(1ll<<i);
					}else{
						break;
					}
				}
				sort(sums.begin(),sums.end(),comp);
			}
		}
	}
	printf("%lld",ans);
}

Measured memory_bytes: 6512
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int w=sc.nextInt()-1,h=sc.nextInt()-1;
        String c=sc.next();
        for(int i=0;i<=h;i++) {
            String s="";
            for(int j=0;j<=w;j++) {
                if(i==(h+1)/2&&j==(w+1)/2) {
                    s+=c;
                }else if((i|j)==0||i==0&&j==w||i==h&&j==0||i==h&&j==w) {
                s+="+";
                }else if(i==0||i==h) {
                   s+="-";
                }else if(j==0||j==w) {
                    s+="|";
                }else {
                    s+=".";
                }
            }
            System.out.println(s);
        }
    }
}


Measured memory_bytes: 26280
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include<complex>
#include<numeric>
using namespace std;
#define MOD 1000000007
#define MOD2 998244353
#define PRIM 3
#define INF (1<<29)
#define LINF (1LL<<60)
#define EPS (1e-10)
#define PI 3.1415926535897932384626433832795028
typedef long long Int;
typedef pair<Int, Int> P;
typedef long double Real;
typedef complex<Real> CP;
 
Int n;
Real a[440000];
Real b[440000];
Real e[440000];
Real c[440000];
 
Real bi_sum[440000];
Real b_sum[440000];
 
vector<P> highs;
set<int> done;
 
int main(){
    cin >> n;
    int mxa = 0;
    for(int i = 0;i < n;i++){
        cin >> a[i];
        a[i+n] = a[i];
        if(a[mxa] < a[i])mxa = i;
    }
    for(int i = 0;i < n;i++){
        cin >> b[i];
        b[i+n] = b[i];
    }
    e[mxa] = e[mxa + n] = a[mxa];
    for(int i = 1;i < n;i++){
        c[mxa + i+1] = - 2 * b[mxa + i] + 2*c[mxa + i] - c[mxa + i-1];
//        cout << c[mxa + i + 1] << endl;
    }
 
    using RP = pair<Real, Real>;
    vector<RP> ch = {{mxa, a[mxa] + c[mxa]}};
 
    for(int i = 1;i <= n;i++){
        RP p = {mxa + i, a[mxa + i] + c[mxa + i]};
        while(ch.size() >= 2){
            RP bb = ch[ch.size() - 2];
            RP b = ch.back();
            bb.first -= p.first;bb.second -= p.second;
            b.first -= p.first;b.second -= p.second;
            if(b.first * bb.second - b.second * bb.first <= 0)ch.pop_back();
            else break;
        }
        ch.push_back(p);
    }
    for(auto p:ch){
//        cout << p.first << " " << p.second << endl;
    }
    Real ans = a[mxa];
    for(int i = 1;i < n;i++){
        int ind = mxa + i;
        auto r = lower_bound(ch.begin(), ch.end(), RP(ind, -INF));
        auto l = prev(r);
        auto l_dist = ind - l->first;
        auto r_dist = r->first - ind;
//        cout << ind << " "  << (l_dist * r->second + r_dist * l->second) /(l_dist + r_dist) - c[ind] << endl;
        ans += (l_dist * r->second + r_dist * l->second) /(l_dist + r_dist) - c[ind]; 
    }
    printf("%.10lf\n", double(ans / n));    
    
    return 0;
}


Measured memory_bytes: 27192
/* ex4_2
    suuxxu */

#include <stdio.h>
#include <math.h>
#define PI 3.14159265358979

int main(void){
    double len_hour, len_minute; // lengths of the hour hand and the minute hand
    double angle; // angle between the hour hand and the minute hand
    double hour, minute;
    double ans;

    // get inputs
    scanf("%lf %lf %lf %lf", &len_hour, &len_minute, &hour, &minute); // A B H M

    // calculate angle(rad)
    angle = (hour + minute / 60) / 12 * 2 * PI - minute / 60 * 2 * PI;

    // calculate answer(cm)
    // use law of cosines
    ans = sqrt(len_hour * len_hour + len_minute * len_minute - 2 * len_hour * len_minute * cos(angle));

    // output answer
    printf("%.10f\n", ans);

    return 0;
}

Measured memory_bytes: 2448
#include<iostream>
using namespace std;
int main(){
    int i,j,n,m;
  cin>>n>>m;
  char s[101][101];
  for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
        cin>>s[i][j];

          for(i=0;i<=m+1;i++)
            cout<<"#";
          cout<<endl;

  for(i=1;i<=n;i++)
    for(j=0;j<=m+1;j++){
        if(j==0||j==m+1)
            cout<<"#";
        else
            cout<<s[i][j];
         if(j==m+1)
            cout<<endl;
    }
  for(i=0;i<=m+1;i++)
            cout<<"#";
          cout<<endl;

}


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

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



Measured memory_bytes: 256
#include <iostream>
using namespace std;
int n,m,a[100],q,ans;
struct qwq
{
	int a,b,c,d;
}b[100];
inline void dfs(int now,int lst)
{
	if(now==n+1)
	{
		int qwq=0;
		for(int i=1;i<=q;i++)
		{
			if(a[b[i].b]-a[b[i].a]==b[i].c)
				qwq+=b[i].d;
		}
		ans=max(ans,qwq);
		return ;
	}
	for(int i=lst;i<=m;i++)
	{
		a[now]=i;
		dfs(now+1,i);
	}
}
int main(int argc, char** argv) {
	cin >> n >> m >> q;
	for(int i=1;i<=q;i++)
		cin >> b[i].a >> b[i].b >> b[i].c >> b[i].d;
	dfs(1,1);
	cout << ans;
	return 0;
}

Measured memory_bytes: 3160
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
bool ok(int siz, int pos, vector<pair<int, int>> v) {
  int l = 1, r = siz;
  reverse(v.begin(), v.end());
  for (int i = 0; i < (int) v.size(); i++) {
    int dir = v[i].first;
    int who = v[i].second;
    if (who == 0) {
      if (dir) {
        r--;
      } else {
        l++;
      }
    } else {
      if (dir) {
        l = max(l - 1, 1);
      } else {
        r = min(r + 1, siz);
      }
    }
    if (l > r) return false;
  }
  return (l <= pos && pos <= r);
}
signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int h, w, n;
  cin >> h >> w >> n;
  int sr, sc;
  cin >> sr >> sc;
  string s, t;
  cin >> s >> t;
  vector<pair<int, int>> vrt, hrz;
  for (int i = 0; i < n; i++) {
    if (s[i] == 'R') {
      hrz.emplace_back(1, 0);
    }
    if (s[i] == 'L') {
      hrz.emplace_back(0, 0);
    }
    if (s[i] == 'U') {
      vrt.emplace_back(0, 0);
    }
    if (s[i] == 'D') {
      vrt.emplace_back(1, 0);
    }
    if (t[i] == 'R') {
      hrz.emplace_back(1, 1);
    }
    if (t[i] == 'L') {
      hrz.emplace_back(0, 1);
    }
    if (t[i] == 'U') {
      vrt.emplace_back(0, 1);
    }
    if (t[i] == 'D') {
      vrt.emplace_back(1, 1);
    }
  }
  if (ok(h, sr, vrt) && ok(w, sc, hrz)) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
  return 0;
}

Measured memory_bytes: 7296
import heapq


n = int(input())
s = list(map(int, input().split()))

# 中央値より左・右の管理
l=[]
r=[]
heapq.heapify(l)
heapq.heapify(r)
lenl=0
lenr=0

# 中央値
x = s[1]

# b含めた答え
ans = s[2]

for i in range(n-1):
    q = list(map(int,input().split()))
    if q[0]==1:
        ans += q[2]
        if lenl>=lenr:
            lenr+=1
            ans+=abs(x-q[1])
            if x<=q[1]:
                heapq.heappush(r,q[1])
            else:
                heapq.heappush(r,x)
                x = -heapq.heappushpop(l,-q[1])
        else:
            lenl+=1
            if x<q[1]:
                heapq.heappush(l,-x)
                x = heapq.heappushpop(r,q[1])
            else:
                heapq.heappush(l,-q[1])
            ans+=abs(x-q[1])
    if q[0]==2:
        print(x, ans)


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

int lcm(int a, int b){
    int i = min(a, b);
    
    while(!(a % i == 0 && b % i == 0)){
        i--;
    }
    
    return i;
}

int main(void){
    int a, b, c;
    cin >> a >> b >> c;
    
    if(c % lcm(a, b) == 0){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define debug(x) cerr << #x << ": " << x << '\n';
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = (int)1e9;
const int MOD = (int)1e9 + 7;

int N;
int A[100];

int main(void){
	cin >> N;
	for(int i = 0; i < N; i++) cin >> A[i];

	bool res = true;
	for(int i = 0; i < N; i++){
		if(A[i]%2 == 0 and A[i]%3 != 0 and A[i]%5 != 0) res = false;
	}

	cout << (res ? "APPROVED" : "DENIED") << '\n';

	return 0;
}

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

int main() {
  vector<int> s(100005,0),a(100005,0);
  vector<bool> isPrime(100005,true);
  int q;
  cin>>q;
  int l,r;
  isPrime[0]=isPrime[1]=false;

  for(int i=2;i*i<=100000;i++) {
    if(isPrime[i]) {
      for(int j=2*i;j<=100000;j+=i) isPrime[j]=false;
    }
  }

  for(int i=0;i<=100000;i++) {
    a[i]=isPrime[i]&&isPrime[(i+1)/2];
  }

  for(int i=0;i<100000;i++) {
    s[i+1]=s[i]+a[i];
  }

  for(int i=0;i<q;i++) {
    cin>>l>>r;
    cout<<s[r+1]-s[l]<<endl;
  }
}


Measured memory_bytes: 3836
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
typedef long long ll;

int vs[200000+10];

int main(void) {
  int K, N;
  scanf("%d%d", &K, &N);
  REP(i, N) {
    scanf("%d", &vs[i]);
  }
  int maxi = vs[0] + K - vs[N-1];
  REP(i, N-1) {
    maxi = max(maxi, vs[i+1] - vs[i]);
  }
  cout << K - maxi << endl;
  return 0;
}


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

typedef long long LL;
const int MN = 200005;

int N, C0, C1, K;
char T[MN];
int stk[MN], cnt[MN], tp;
LL Ans;

int main() {
	scanf("%s", T + 1), N = strlen(T + 1);
	for (int i = 1; i <= N; ++i) ++(T[i] & 1 ? C1 : C0);
	Ans = (LL)(C1 + 1) * (C1 + 1) / 4;
	T[0] = T[N + 1] = '0';
	for (int i = 0; i <= N + 1; ++i) {
		int x = T[i] - '0';
		if (!x) {
			if (tp && !stk[tp]) ++cnt[tp];
			else stk[++tp] = 0, cnt[tp] = 1;
		} else {
			if (tp && stk[tp]) --tp, Ans += C0;
			else stk[++tp] = 1, cnt[tp] = 1;
		}
	} --cnt[1], --cnt[tp];
	for (int i = 1, s = 0; 2 * i <= tp; ++i)
		s += cnt[2 * i - 1],
		Ans += (s + i + 1) / 2 - (i + 1) / 2 + (C0 - s);
	printf("%lld\n", Ans);
	return 0;
}

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

int main() {
    int a,b,c;
    cin >> a >> b >> c;
    if(a==b){
        cout << c << endl;
    }else if (b==c){
        cout << a <<endl;
    }else{
        cout << b << endl;
    }
    

    return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace Contest
{
    class Scanner
    {
        private string[] line = new string[0];
        private int index = 0;
        public string Next()
        {
            if (line.Length <= index)
            {
                line = Console.ReadLine().Split(' ');
                index = 0;
            }
            var res = line[index];
            index++;
            return res;
        }
        public int NextInt()
        {
            return int.Parse(Next());
        }
        public long NextLong()
        {
            return long.Parse(Next());
        }
        public string[] Array()
        {
            line = Console.ReadLine().Split(' ');
            index = line.Length;
            return line;
        }
        public int[] IntArray()
        {
            return Array().Select(int.Parse).ToArray();
        }
        public long[] LongArray()
        {
            return Array().Select(long.Parse).ToArray();
        }
    }

    class HashMap<K, V> : Dictionary<K, V>
    {
        new public V this[K i]
        {
            get
            {
                V v;
                return TryGetValue(i, out v) ? v : base[i] = default(V);
            }
            set { base[i] = value; }
        }
    }

    class Program
    {
        private HashMap<int, int> Map = new HashMap<int, int>();
        private void Scan()
        {
            var sc = new Scanner();
            var N = sc.NextInt();
            for (int i = 0; i < N; i++)
            {
                Map[sc.NextInt()]++;
            }
        }

        public void Solve()
        {
            Scan();
            int ans = 0;
            foreach (var p in Map)
            {
                if(p.Value>=p.Key)
                {
                    ans += p.Value - p.Key;
                }
                else
                {
                    ans += p.Value;
                }
            }
            Console.WriteLine(ans);
        }

        static void Main(string[] args)
        {
            new Program().Solve();
        }
    }
}

Measured memory_bytes: 27488
#include<stdio.h>
#include<string.h>


int main(){
	
	char angka[1005];
	int count2;
	
	scanf("%s",angka);getchar();
	
	int len = strlen(angka);
	
	count2=0;
	for (int i=0;i<len;i++){
		
		if(angka[i]=='2'){
			count2++;		
		}
		
	}
	
	printf("%d\n",count2);
	
	return 0;	
}

Measured memory_bytes: 128
H,W = map(int,raw_input().split())
 
s = []
for i in range(H):
	s.append(raw_input())
 
flag=True
for i in range(H):
	for j in range(W):
		if s[i][j]=='#':
			local_flag=False
			if i+1<H:
				if s[i+1][j]=='#':
					local_flag=True
			if j+1<W:
				if s[i][j+1]=='#':
					local_flag=True
			if i-1>=0:
				if s[i-1][j]=='#':
					local_flag=True
			if j-1>=0:
				if s[i][j-1]=='#':
					local_flag=True
			if local_flag==False:
				flag=False
if flag:
	print 'Yes'
else:
	print 'No'

Measured memory_bytes: 2692
#include <iostream>
#include <queue>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

int v[1001][1001];

int done[1000][1000] = {};

struct NODE{
	int x,y,c;
	NODE(int x,int y,int c) : x(x) , y(y) , c(c) {}
};
bool operator < (const NODE &a,const NODE &b){
	return a.c > b.c;
}

int main(){
	int H,W;
	cin >> W >> H;
	int gx,gy;
	for(int i = 0 ; i < H ; i++){
		for(int j = 0 ; j < W ; j++){
			char c;cin >> c;
			if( c == 't' ){
				gx = j;
				gy = i;
				v[i][j] = 0;
			}else if( c == '#' ) v[i][j] = 1e9;
			else v[i][j] = 0;
		}
	}
	int n;
	cin >> n;
	
	for(int i = 1 ; i <= n ; i++){
		int x,y;
		cin >> x >> y;
		v[y][x] = i;
	}
	priority_queue<NODE> Q;
	Q.push(NODE(0,0,0));
	int dx[] = {-1,0,1,0};
	int dy[] = {0,1,0,-1};
	
	while(Q.size()){
		NODE q = Q.top(); Q.pop();
		if( q.c == 1e9 ) continue;
		if( q.y == gy && q.x == gx ) {
			cout << q.c << endl;
			return 0;
		}
		if( done[q.y][q.x]++ ) continue;
		for(int i = 0 ; i < 4 ; i++){
			int tx = q.x + dx[i];
			int ty = q.y + dy[i];
			if( tx < 0 || ty < 0 || tx >= W || ty >= H ) continue;
			Q.push(NODE(tx,ty,max(q.c,v[ty][tx])));
		}
	}
	cout << -1 << endl;
	
}

Measured memory_bytes: 35136
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <climits>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <random>
#include <cctype>
#include <complex>
#include <regex>

using namespace std;

#define C_MAX(a, b) ((a)>(b)?(a):(b))
#define SHOW_VECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";}
#define SHOW_MAP(v) {std::cerr << #v << endl; for(const auto& xxx: v){std::cerr << xxx.first << " " << xxx.second << "\n";}}


int main() {

    int N, C;
    cin >> N >> C;

    vector<int> s(N), t(N), c(N);
    for (int i = 0; i < N; i++) cin >> s[i] >> t[i] >> c[i], c[i]--;

    vector<vector<pair<int, int>>> channels(C, vector<pair<int, int> >());
    for (int i = 0; i < N; i++) channels[c[i]].push_back(make_pair(s[i], t[i]));
    for (int i = 0; i < C; i++) sort(channels[i].begin(), channels[i].end());

    vector<vector<pair<int, int>>> newChannels(C, vector<pair<int, int>>());
    for (int i = 0; i < C; i++) {
        for (int j = 0; j < channels[i].size(); j++) {
            if (j == 0) newChannels[i].push_back(channels[i][j]);
            else {
                if (newChannels[i].back().second == channels[i][j].first) newChannels[i].back() = make_pair(newChannels[i].back().first, channels[i][j].second);
                else newChannels[i].push_back(channels[i][j]);
            }
        }
    }
    for (int i = 0; i < C; i++) for (int j = 0; j < newChannels[i].size(); j++) newChannels[i][j].first--;
   // for (int i = 0; i < C; i++) SHOW_MAP(newChannels[i]);

    vector<int> times(100010, 0);
    for (int i = 0; i < C; i++)for (int j = 0; j < newChannels[i].size(); j++) times[newChannels[i][j].first]++, times[newChannels[i][j].second]--;
    for (int i = 0; i < times.size() - 1; i++) times[i + 1] += times[i];

    int ans = INT_MIN;
    for (int i = 0; i < times.size(); i++) ans = max(ans, times[i]);
    cout << ans << endl;

    return 0;
}




























Measured memory_bytes: 3968