akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>

using namespace std;

void riful(int[], int);
void cut(int[], int, int);

int main(){
  int n, m, i;
  int card[200];
  for(i = 0; i < 200; i++){
      card[i] = -1;
  }
  cin >> n >> m;
  for(i = 0; i < 200; i++){
    if(i < n * 2)
      card[i] = i;
    else
      card[i] = -1;
  }
  for(i = 0; i < m; i++){
    int k;
    cin >> k;
    if(k == 0)
      riful(card, n);
    else
      cut(card, n, k);
  }
  for(i = 0; i < n * 2; i++){
    printf("%d\n", card[i] + 1);
  }
  return 0;
}

void riful(int card[], int n){
  int A[100], B[100], i;
  for(i = 0; i < 100; i++){
    A[i] = B[i] = -1;
  }
  for(i = 0; i < n; i++){
    A[i] = card[i];
    B[i] = card[n + i];
  }
  for(i = 0; i < n; i++){
    card[i * 2] = A[i];
    card[i * 2 + 1] = B[i];
  }
}

void cut(int card[], int n, int k){
  int A[200], B[200], i;
  for(i = 0; i < n * 2; i++){
    if(i < k)
      A[i] = card[i];
    else
      B[i - k] = card[i];
  }
  for(i = 0; i < n * 2; i++){
    if(i < n * 2 - k)
      card[i] = B[i];
    else
      card[i] = A[i - (n * 2 - k)];
  }
}

Measured memory_bytes: 1144
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

class Restaurant {
    String city;
    int point;
    int i;
    public Restaurant(String city, int point, int i) {
        this.city = city;
        this.point = point;
        this.i = i;
    }
}
class RestaurantComparator implements Comparator<Restaurant>{
    @Override
    public int compare(Restaurant o1, Restaurant o2) {
        if(o1.city.compareTo(o2.city) < 0 ) {
            return -1;
        } else if(o1.city.compareTo(o2.city) > 0) {
            return 1;
        } else {
            return Integer.compare(o2.point, o1.point);
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        List<Restaurant> list = new ArrayList<Restaurant>();
        int n = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            String city = sc.next();
            int point = sc.nextInt();
            list.add(new Restaurant(city, point, i));
        }
        Collections.sort(list, new RestaurantComparator());
        for (Restaurant restaulant: list) {
            System.out.println(restaulant.i);
        }
    }
}

Measured memory_bytes: 36064
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define FOR(i, a, n) for (int i = (a); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
using namespace std;

class HopcroftKarp {
    void bfs() {
        const int n = g.size();
        dist.assign(n, -1);
        queue<int> que;
        for (int i = 0; i < n; ++i) if (!used[i]) {
            que.push(i);
            dist[i] = 0;
        }
        while (!que.empty()) {
            int v = que.front();
            que.pop();
            for (int& u : g[v]) {
                int w = match[u];
                if (w >= 0 && dist[w] == -1) {
                    dist[w] = dist[v] + 1;
                    que.emplace(w);
                }
            }
        }
    }

    bool dfs(int v) {
        vv[v] = true;
        for (auto& u : g[v]) {
            int w = match[u];
            if (w < 0 || (!vv[w] && dist[w] == dist[v] + 1 && dfs(w))) {
                match[u] = v;
                used[v] = true;
                return true;
            }
        }
        return false;
    }
    
public:
    vector<vector<int>> g;
    vector<int> dist, match;
    vector<bool> used, vv;

    HopcroftKarp(int n, int m) : g(n), match(m, -1), used(n) {}

    void add_edge(int u, int v) {
        g[u].push_back(v);
    }

    int bipartite_matching() {
        const int n = g.size();
        int res = 0;
        while (true) {
            bfs();
            vv.assign(n, false);
            int flow = 0;
            for (int i = 0; i < n; ++i) {
                if (!used[i] && dfs(i)) ++flow;
            }
            if (!flow) break;
            res += flow;
        }
        return res;
    }

    void print() {
        for (int i = 0; i < match.size(); ++i) {
            if (~match[i]) cout << match[i] << " - " << i << endl;
        }
    }
};

int N;
int a[100], b[100], c[100], d[100];

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

    cin >> N;
    REP (i, N) cin >> a[i] >> b[i];
    REP (i, N) cin >> c[i] >> d[i];
    HopcroftKarp g(N, N);
    REP (i, N) REP (j, N) {
        if (a[i] < c[j] && b[i] < d[j]) {
            g.add_edge(i, j);
        }
    }
    cout << g.bipartite_matching() << endl;
}

Measured memory_bytes: 256
n,m=map(int,input().split())
x=list(map(int,input().split()))
x.sort()
w=[[] for i in range(m-1)]
for i in range(m-1):
    w[i]=[x[i],x[i+1]-x[i]]
w=sorted(w,key=lambda y:y[1])
w.reverse()
skip=[]
if m!=1:
    for i in range(n-1):
        skip.append(w[i])
        if i==m-2:
            break
            
    skip=sorted(skip,key=lambda y:y[0])
ans=[]
k=x[0]
for i in skip:
    ans.append(i[0]-k)
    k=i[0]+i[1]
ans.append(x[m-1]-k)
print(sum(ans))

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

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> b(n);
    vector<int> c(n-1);
    rep(i,n) cin >> a[i];
    rep(i,n) cin >> b[i];
    rep(i,n-1) cin >> c[i];

    int ans = 0, prev = -1;

    rep(i,n){
        ans += b[a[i]-1];
        if(prev+1 == a[i]){
            ans += c[prev-1];
        }
        prev = a[i];
    }
    cout << ans << endl;
}



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

int gcd(int a,int b){
    if(a%b==0)
    	return b;
    else
        return gcd(b,a%b);
}
int main(){
	int k;
	int sum=0;
	cin>>k;
	for(int i=1;i<=k;i++){
		for(int j=1;j<=k;j++){
			for(int n=1;n<=k;n++){
				 int x=gcd(i,j);
				 int y=gcd(x,n);
				 sum+=y;
			}
		}
	}
	cout<<sum;
	return 0;
}

Measured memory_bytes: 3672
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define N_MAX 10000
#define S_MAX 100000000

int main(){
  int i,j=0,c=0,n,A[N_MAX],flag;
  double sqrtNum;
  scanf("%d",&n);
  if(n>N_MAX || n<=0)exit(8);
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
    if(A[i]>S_MAX || A[i]<2)exit(8);
  }
  
  for(j=0;j<n;j++){
    /*
    flag=0;
    if(A[j]%2==0 && A[j]!=2)flag=1;
    else{
      for(i=3;i<A[j];i+=2){
	if(A[j]%i==0){
	  flag=1;
	  break;
	}
      }
    }
    if(flag==0)c++;
    */
    flag=0;
    if(A[j]%2==0 && A[j]!=2){
      flag=1;
    }
    else{
    sqrtNum = sqrt(A[j]);
    for(i=3;i<=sqrtNum;i+=2){
      if(A[j]%i==0){
	flag=1;
	break;
      }    
    }
    if(flag==0)c++;
    }
  }
  printf("%d\n",c);
  return 0;
}
  



Measured memory_bytes: 2124
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<list>
#include<cstdint>
#include<bits/stdc++.h>
#include<queue>
#include<set>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep_r(i, n) for(int i = n-1; i >= 0; i--)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i++)
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((ll)(x).size())
#define bit(n) (1LL<<(n))
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define INF bit(60)
#define pb push_back
#define mod 1000000007

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

using namespace std;
using uif=uint_fast64_t;
using ll=long long int;

int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a%mod;a=1ll*a*a%mod;}while(b>>=1);return ans;}
int qp(int a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}

int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};


#define FACSIZE 2002

ll invfac[FACSIZE];
ll fac[FACSIZE];

ll mod_pow(ll ,ll );
ll mod_add(ll ,ll );
ll mod_mul(ll ,ll );
ll mod_div(ll ,ll );
void make_fact(ll );
void make_invfact(ll );



int main(void){
  using pa=pair<ll,ll>;
  ll n,m;
  cin>>n>>m;
  vector<ll> a(n);
  rep(i,n) cin>>a[i];
  vector<ll> b(m);
  vector<ll> c(m);
  priority_queue< pa,vector<pa>,greater<pa> > pq;
  unordered_map<ll,ll> um;
  rep(i,m){
    cin>>b[i]>>c[i];
  }
  for(auto x:a){
    um[x]++;
  }
  for(auto p:um) pq.push(p);
  
  for(ll i=0;i<m;i++){
    ll rep_num=c[i];
    ll rep_cnt_max=b[i];
    ll cnt=0;
    while( !pq.empty() ){
      if(pq.top().second + cnt > rep_cnt_max ) break;
      else if( pq.top().first >= rep_num ) break;
      auto p=pq.top();
      pq.pop();
      cnt+=p.second;
    }
    auto diff = rep_cnt_max - cnt;
    if(!pq.empty() && pq.top().first < rep_num ){
      auto p=pq.top();
      pq.pop();
      p.second -= diff;
      cnt+=diff;
      if(p.second>0) pq.push(p);
    }
    if(cnt>0) pq.push( make_pair( rep_num ,cnt) );
  }
  ll ans=0;
  while(!pq.empty()){
    auto p=pq.top();
    pq.pop();
    //cout << p.first << "," << p.second << endl;
    ans+=p.first*p.second;
  }
  cout << ans << endl;
  return 0;

}

ll mod_pow(ll x,ll r){
  if(r==0) return 1;
  else if(r==1) return x%mod;
  else if(r%2==0){
    ll t=mod_pow(x,r/2)%mod;
    return t*t %mod;
  } 
  else{
    ll t=mod_pow(x,r/2)%mod;
    ll k= t*t %mod;
    return k*x%mod;
  } 
}
ll mod_add(ll a,ll b){
  return (a+b)%mod;
}

ll mod_mul(ll a,ll b){
  return (a*b)%mod;
}

ll mod_div(ll a,ll b){
  return mod_mul(a,mod_pow(b,mod-2));
}

void make_fact(ll n){
  fac[0]=1;
  rep(i,n){
    fac[i+1]=mod_mul(fac[i],i+1);
  }  
}

void make_invfact(ll n){
  invfac[n]= mod_pow( fac[n] ,mod-2);
  for(int i=n-1;i>=0;i--){
    invfac[i]=mod_mul(invfac[i+1],i+1);
  }

}


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

#define rep(i,z) for(int i = 0; i<(int)(z); i++)
#define rep1(i,z) for(int i = 1; i<=(int)(z); i++)
 
using namespace std;

typedef long long ll;
const ll MOD=1e9+7;
using pear = pair<int,int>;

int main(){
   string s; cin>>s;
   if(s=="ABC")cout<<"ARC"<<endl;
   else cout<<"ABC"<<endl;
}

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

#define pb push_back
#define mp make_pair
#define fst first
#define snd second

#define fr(i,n) 	for(int i=0;i<n;i++)
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)

int main(){
    string s; cin >> s;
    int n = s.size();
    int a0 = -1, zf = -1;
    fr(i, n){
        if(s[i] == 'A' && a0 == -1) a0 = i;
        else if(s[i] == 'Z') zf = max(zf, i);
    }
    cout << zf - a0 + 1 << endl;

}


Measured memory_bytes: 640
s = int(input())

def function(n):
    if (n % 2 == 0):
        n = int(n/2)
    else:
        n = int(3*n + 1)

    return n

m = 10**6
num_li = []
num_li.append(s)
for i in range(m):
    if(function(num_li[i]) in num_li):
        print(i+2)
        break
    else:
        num_li.append(function(num_li[i]))
    
        

Measured memory_bytes: 3060
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define ULL unsigned LL
#define PII pair<int,int>
#define VI vector<int>
#define VPII vector< PII >
#define VVI vector< VI >
#define PB push_back
#define F first
#define S second
const int INF=1e9;
const int MOD=1e9+7;
int n,m;
map<int,int> cnt;
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int x;
        scanf("%d",&x);
        cnt[x]++;
    }
    scanf("%d",&m);
    for(int i=0;i<m;i++){
        int x;
        scanf("%d",&x);
        if(cnt[x]>0){
            cnt[x]--;
        }
        else return 0*puts("NO");
    }
    puts("YES");
    return 0;
}

Measured memory_bytes: 11648
#include <bits/stdc++.h>
#define N 200010
#define f first
#define int long long
#define s second
using namespace std;
typedef pair<int, int> pii;

int n, m, q, pai[N], peso[N];

int k, nao;

vector<pii> T;

int Find(int x)
{
	if(x == pai[x]) return x;

	return pai[x] = Find(pai[x]);
}

void join(int a, int b)
{
	a = Find(a), b = Find(b);

	if(a == b) return;

	k --;

	if(peso[a] > peso[b]) swap(a, b);

	pai[a] = b;

	if(peso[a] == peso[b]) peso[b] ++;
}

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

	cin>>n>>m>>q;

	for(int i = 0; i < n; i++) pai[i] = i;

	k = n;

	for(int i = 0; i < q; i++)
	{
		int a, b, c;

		cin>>a>>b>>c;

		if(c == 0)
		{
			if(Find(a) != Find(b))
				join(a, b);
			//else nao = 1;
		}

		else T.push_back({a, b});
	}

	if(nao) cout<<"No\n", exit(0);

	if(m == n - 1 and T.empty()) cout<<"Yes\n", exit(0);

	if(m == n - 1 and !T.empty()) cout<<"No\n", exit(0);

	for(auto w: T)
		if(Find(w.f) == Find(w.s))
		{
			cout<<"No\n";

			exit(0);
		}

	int dhi = (n + k*(k - 1)/2 - k);

	if(m <= dhi) cout<<"Yes\n";

	else cout<<"No\n";
}

Measured memory_bytes: 3188
X,N = [int(i) for i in input().split()]
if N == 0:
    print(X)
    exit()
p = [int(i) for i in input().split()]
if not X in p:
    print(X)
    exit()
for i in range(1,100):
    if not X-i in p:
        print(X-i)
        exit()
    if not X+i in p:
        print(X+i)
        exit()

Measured memory_bytes: 61752
#include <iostream>
#include <vector>
using namespace std;
int main(){

  int n,q;
  vector<int> a;
  cin>>n;
  for(int i=0,t;i<n&&cin>>t;i++) a.push_back(t);
  cin>>q;
  for(int i=0;i<q;i++){
    int b,e,t;
    cin>>b>>e>>t;
    for(int j=b;j<e;j++) swap(a[j],a[j-b+t]);
  }
  for(int i=0;i<n;i++){
    if(i) cout<<" ";
    cout<<a[i];
  }
  cout<<endl;
  return 0;
}



Measured memory_bytes: 3136
#include <cstdio>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

vector<int> a(12, 4);
vector<int> washizu(12, 0);
vector<bool> ret(12, false);

void solve(int i, int n)
{
    if(n == 0){
        vector<int> select(12, 0);
        for(int j=0; j<12; ++j)
            select[j] = 4 - a[j];

        for(int j=0; j<12; ++j){ // 対子
            if(a[j] < 2)
                continue;

            select[j] += 2;

            bool ok = true;
            for(int k=0; k<12; ++k){
                if(select[k] < washizu[k])
                    ok = false;
            }

            if(ok){
                for(int k=0; k<12; ++k){
                    if(select[k] > washizu[k])
                        ret[k] = true;
                }
            }

            select[j] -= 2;
        }
        return;
    }

    if(i < 12){ // 刻子
        if(a[i] >= 3){
            a[i] -= 3;
            solve(i+1, n-1);
            a[i] += 3;
        }
        solve(i+1, n);
    }else if(i < 22){ // 順子
        int j = i - 12;
        if(a[j] > 0 && a[j+1] > 0 && a[j+2] > 0){
            -- a[j];
            -- a[j+1];
            -- a[j+2];
            solve(i, n-1);
            ++ a[j+2];
            ++ a[j+1];
            ++ a[j];
        }
        solve(i+1, n);
    }
}

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

    for(int i=0; i<3*n+1; ++i){
        string s;
        cin >> s;
        if(s != "*"){
            int x = atoi(s.c_str());
            -- x;
            ++ washizu[x];
        }
    }

    solve(0, n);

    bool ng = true;
    for(int i=0; i<12; ++i){
        if(ret[i]){
            cout << (i + 1) << endl;
            ng = false;
        }
    }
    if(ng)
        cout << -1 << endl;

    return 0;
}

Measured memory_bytes: 1220
#include <iostream>
#include <algorithm>
#include <complex>
#include <string>
#include <vector>

using namespace std;

int main() {

  int n;
  int l, r;
  int ans = 0;

  cin >> n;

  for (int i = 0; i < n; i++) {
    cin >> l >> r;
    ans += r - l + 1;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; ++i)
#define rrep(i, n) for(int i = n-1; i >= 0; --i)
#define fi first
#define se second
using namespace std;
using lint = long long;
using uint = unsigned int;
using ulint = unsigned long long;
using ldouble = long double;
using pii = pair<int, int>;
using pli = pair<lint, lint>;
using pdd = pair<double, double>;
using pld = pair<ldouble, ldouble>;
using v1i = vector<int>;
using v1li = vector<lint>;
using v2i = vector<vector<int>>;
using v2li = vector<vector<lint>>;
using v3i = vector<vector<vector<int>>>;
using v3li = vector<vector<vector<lint>>>;
using v1b = vector<bool>;
using v2b = vector<vector<bool>>;
using v3b = vector<vector<vector<bool>>>;
using v1c = vector<char>;
using v2c = vector<vector<char>>;
using v3c = vector<vector<vector<char>>>;
constexpr lint mod1 = 1e9+7;
constexpr lint mod2 = 998244353;

long inv(long long a, long long mod){
  long long s = 1, tmp = a, t = mod - 2;
  while(t > 0){
    if(t % 2 == 1){
      s *= tmp;
      s %= mod;
    }
    t /= 2;
    tmp *= tmp;
    tmp %= mod;
  }
  return s;
}

int main(){
  int s, n; cin >> s; n = s / 3; long ans = 0;
  v1li a(2000, 1), b(2000, 1);
  rep(i, 2000){
    a[i+1] = a[i] * (i+1) % mod1;
    b[i+1] = b[i] * inv(i+1, mod1) % mod1;
  }
  rep(i, n){
    int tmp = s - 2 * (i+1); long t = 1;
    if(tmp < i+1) break;
    (t *= a[tmp-1] * b[tmp-1-i]) %= mod1;
    (t *= b[i]) %= mod1;
    (ans += t) %= mod1;
  }
  cout << ans;
  return 0;
}

Measured memory_bytes: 3540
#include<stdio.h>
int main(){
    long long int N,sum=0;
    scanf("%lld", &N);
    long long int d = 0; 
    for(int i = 1; i<1000000; i++){
        if(i==d) break;        
        if(N%i == 0){
            d = N/i;
            if(d==1) break;
            if(N/(d-1) == N%(d-1))            
            sum += d-1;
        }
    }
    
    printf("%lld\n",sum);
    return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<limits>
#include<sstream>      

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;

const int inf = numeric_limits<int>::max() /4;
const ll linf = numeric_limits<ll>::max() /4;
const ull ulinf = numeric_limits<ull>::max()/4;
const double pi = acos(-1);
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const int dx8[8]={-1,0,1,-1,1,-1,0,1};
const int dy8[8]={-1,-1,-1,0,0,1,1,1};

#define p_queue(i) priority_queue<i> 
#define rp_queue(i) priority_queue<i, vector<i>, greater<i>> 
#define P(p) cout<<(p)<<endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define mod(i) ((i)%(ll)(1e9 + 7))
#define divm(a,b) (mod(a * modpow((ll)b,(ll)(1e9+5))))
#define rsort(a,b,c) sort(a, b, greater<c>())
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.end(), v.begin());
#define ft first
#define sd second
#define pb push_back
#define it insert
#define sz(x) ((int)(x).size())
#define lb(a,n,k) (lower_bound(a,a+n,k) - a) 
#define vlb(a,k)  (lower_bound(a.begin(),a.end(),k) - a.begin())
#define ub(a,n,k) (upper_bound(a,a+n,k) - a) 
#define vub(a,k)  (upper_bound(a.begin(),a.end(),k) - a.begin())
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return

ll modpow(ll i,ll j){ ll tmp=1; while(j){ if(j%2)tmp=mod(tmp*i);i=mod(i*i);j/=2;}return tmp;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

vector<string> split(const string &str, char sep){
    vector<string> v;
    stringstream ss(str);
    string buffer;
    while( getline(ss, buffer, sep) ) {
        v.push_back(buffer);
    }
    return v;
}

//ll ncr[100][100];
//ll nCr(int n, int r){if(n==r) ret ncr[n][r] = 1; if(r==0) ret ncr[n][r] = 1; if(r==1) ret ncr[n][r] = n;if(ncr[n][r]) ret ncr[n][r]; ret ncr[n][r] = nCr(n-1,r) + nCr(n-1,r-1);}

//ll npr[100][100]={};
//ll nPr(int n,int r){if(npr[n][r])ret npr[n][r];if(r==0)ret npr[n][r] = 1;if(r==1)ret npr[n][r] = n;ret npr[n][r] = n * nPr(n-1,r-1);}

//ll nHr(int n,int r){ret nCr(n+r-1,r);}

///////////////////////////////////////////////////////////////////////////



int main(){

    int n;
    cin >> n;
    ll k = 0,g = 0;
    
    ll a;
    
    rep(i,0,n){
         cin >> a;
         if(a%2 == 0)g++;
         else k++;
    }
    g += k/2;
    k %= 2;

    if(k == 1){
        NO;
    }else{
        YES;
    }
    
	return  0;
}

Measured memory_bytes: 256
import math
n=int(input())
al=list(map(int,input().split()))
a=['{:060b}'.format(x) for x in al]
a=''.join(a)

m=math.ceil(math.log(max(1,max(al)),2))

ans=0
for i in range(m):
  sum1=a[59-i::60].count('1')
  sum0=n-sum1
  ans+=2**i*sum1*sum0

print(ans%(10**9+7))

Measured memory_bytes: 72948
// X: Yet Another Die Game
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    ll x;
    cin >> x;
    ll ans=x/11*2;
    if(x%11!=0 && x%11<=6){ans++;}
    else if(x%11>=7){ans+=2;}
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3592
from collections import Counter
h, w = map(int, input().split())
C = [[0]*10 for _ in range(10)]
cost = []
for i in range(10):
    C[i] = list(map(int, input().split()))

for k in range(10):
    for i in range(10):
        for j in range(10):
            C[i][j] = min(C[i][j], C[i][k]+C[k][j])
costs = [C[i][1] for i in range(10)]

A = Counter()
for i in range(h):
    A += Counter(list(map(int,input().split())))

ans = 0
for key, val in A.items():
    if key!=-1:
        ans += val*costs[key]
print(ans)

Measured memory_bytes: 9500
N = int(input())
s = [int(input()) for i in range(N)]
s.sort()
ans = 0
check = 0
for i in s:
    if i % 10 != 0:
        check = 1
        break

if check == 0:
    ans = 0
else:
    ans = sum(s)
    if ans % 10 == 0:
        for i in s:
            if i % 10 != 0:
                ans -= i
                break

print(ans)


Measured memory_bytes: 9068
N, M = [int(v) for v in input().split()]
a = [int(v) for v in input().split()]
a.sort(reverse=True)

num_dict = {
    1: 2,
    2: 5,
    3: 5,
    4: 4,
    5: 5,
    6: 6,
    7: 3,
    8: 7,
    9: 6
}

INF = (1<<20)
dp = [-INF] * (N+1)
dp[0] = 0

for i in range(1, N+1):
    max_digit = -1
    for v in a:
        if num_dict[v] > i:
            continue
        max_digit = max(max_digit, dp[i - num_dict[v]] + 1)
    if max_digit > 0:
        dp[i] = max_digit

ans = ''
ret = N
while ret > 0:
    for v in a:
        if num_dict[v] > ret:
            continue
        if dp[ret - num_dict[v]] == dp[ret] - 1:
            ans += str(v)
            ret -= num_dict[v]
            break

print(ans)


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

using namespace std;

int cntSwap;

void bubbleSort(int A[], int N) {
	for (int i = 1; i < N; i++) {
		int j = i - 1;
		while (j >= 0 && A[j] > A[j + 1]) {
			swap(A[j], A[j + 1]);
			cntSwap++;
			j--;
		}
	}
}

void printArray(int A[], int N) {
	for(int i = 0; i < N - 1; i++)
		cout << A[i] << " ";
	cout << A[N-1] << endl;;
}


int main() {
	int N;
	cin >> N;
	int A[N];
	for (int i = 0; i < N; i++)
		cin >> A[i];
	bubbleSort(A, N);
	printArray(A, N);
	cout << cntSwap << endl;
}

Measured memory_bytes: 3076
#include<bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP2(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(v) (v).begin(),(v).end()
#define INF 2e9
typedef long long ll;

int main()
{
  int n;
  cin>>n;
  vector<int> a(n),b(n),c(n);
  REP(i,n) cin>>a[i];
  REP(i,n) cin>>b[i];
  REP(i,n) cin>>c[i];
  sort(ALL(a));
  sort(ALL(b));
  sort(ALL(c));

  ll ans=0;
  REP(j,n){
    auto i=lower_bound(ALL(a),b[j])-a.begin(),k=c.end()-upper_bound(ALL(c),b[j]);
    ans+=i*k;
  }
  cout<<ans<<endl;

  return 0;
}

Measured memory_bytes: 1536
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>

#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;


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

	if (N < 10)
	{
		cout << R+100*(10-N) << endl;
	}
	else
	{
		cout << R << endl;

	}

	return 0;
}




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

int main(){
    int N;
    cin >> N;
    cout << N * N * N << endl;
}


Measured memory_bytes: 256
# include "bits/stdc++.h"
using namespace std;
using LL = long long;
using ULL = unsigned long long;
const double PI = acos(-1);
template<class T>constexpr T INF() { return ::std::numeric_limits<T>::max(); }
template<class T>constexpr T HINF() { return INF<T>() / 2; }
template <typename T_char>T_char TL(T_char cX) { return tolower(cX); };
template <typename T_char>T_char TU(T_char cX) { return toupper(cX); };
const int vy[] = { -1, -1, -1, 0, 1, 1, 1, 0 }, vx[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
const int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
int popcnt(unsigned long long n) { int cnt = 0; for (int i = 0; i < 64; i++)if ((n >> i) & 1)cnt++; return cnt; }
int d_sum(LL n) { int ret = 0; while (n > 0) { ret += n % 10; n /= 10; }return ret; }
int d_cnt(LL n) { int ret = 0; while (n > 0) { ret++; n /= 10; }return ret; }
LL gcd(LL a, LL b) { if (b == 0)return a; return gcd(b, a%b); };
LL lcm(LL a, LL b) { LL g = gcd(a, b); return a / g*b; };
# define ALL(qpqpq)           (qpqpq).begin(),(qpqpq).end()
# define UNIQUE(wpwpw)        sort(ALL((wpwpw)));(wpwpw).erase(unique(ALL((wpwpw))),(wpwpw).end())
# define LOWER(epepe)         transform(ALL((epepe)),(epepe).begin(),TL<char>)
# define UPPER(rprpr)         transform(ALL((rprpr)),(rprpr).begin(),TU<char>)
# define FOR(i,tptpt,ypypy)   for(LL i=(tptpt);i<(ypypy);i++)
# define REP(i,upupu)         FOR(i,0,upupu)

struct INIT{
    INIT(){
        std::ios::sync_with_stdio(false);
        std::cin.tie(0);
        cout << fixed << setprecision(13);
    }
}INIT;

int n;
pair<int, int> p[101010], q[101010];

bool calc(pair<int, int> a, pair<int, int> b){
    return a.second < b.second;
}

int main(){
    cin >> n;
    REP(i, n)cin >> p[i].first >> p[i].second;
    REP(i, n)q[i].first = p[i].first - p[i].second, q[i].second = p[i].first + p[i].second;
    sort(q, q + n, calc);
    int ans = 1;
    int pre = 0;
    for(int i = 1;i < n;i++){
        if(q[pre].second <= q[i].first){
            ans++;
            pre = i;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 1792
N=int(input())
V=list(map(int,input().split()))
C=list(map(int,input().split()))
A=[]
cnt=0
for i in range(N):
    A.append(V[i]-C[i])
for j in range(N):
    if A[j]>=0:
        cnt+=A[j]
print(cnt)


Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <map>
#include <bitset>
#include <string>
#include <queue>
#include <sstream>
#include <algorithm>

using namespace std;

const int kInf = 0x3F3F3F3F;

template <class T>
vector<T> Dijkstra(
            vector<vector<T> >& g,
            typename vector<T>::size_type s
) {
  typedef typename vector<T>::size_type size_type;

  size_type MAX_SIZE = numeric_limits<size_type>::max();
  size_type n = g.size();

  vector<T> d(n, kInf);
  vector<size_type> pa(n, MAX_SIZE);
  d[s] = 0;
  priority_queue<pair<size_type, T> > q;
  q.push(make_pair(s, 0));

  while (!q.empty()) {
    const size_type u = q.top().first;
    const T cost = -q.top().second;
    q.pop();
    for (size_type v = 0; v < n; v++) {
      if (v == s) { continue; }
      const T c = d[u] + g[u][v];
      if (d[v] > c) {
        d[v] = c;
        pa[v] = u;
        q.push(make_pair(v, -c));
      }
    }
  }

  return d;
}

int main(int argc, char const *argv[]) {
  long ans = 0;
  int h, w;

  cin >> h >> w;
  vector<vector<int>> g(10, vector<int>(10));
  for (int i = 0; i < 10; ++i) {
    for (int j = 0; j < 10; ++j) {
      cin >> g[j][i];
    }
  }

  vector<int> count(10, 0);
  for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w; ++j) {
      int num;
      cin >> num;
      if (num == -1) { num = 1; }
      ++count[num];
    }
  }

  auto diss = Dijkstra(g, 1);
  for (int i = 0; i < 10; ++i) {
    ans += count[i] * diss[i];
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[1005]; 
int main()
{
	int x;cin>>x;
	if(x>=400&&x<=599) cout<<'8'<<endl;
	if(x>=600&&x<=799) cout<<'7'<<endl;
	if(x>=800&&x<=999) cout<<'6'<<endl;
	if(x>=1000&&x<=1199) cout<<'5'<<endl;
	if(x>=1200&&x<=1399) cout<<'4'<<endl;
	if(x>=1400&&x<=1599) cout<<'3'<<endl;
	if(x>=1600&&x<=1799) cout<<'2'<<endl;
	if(x>=1800&&x<=1999) cout<<'1'<<endl;
} 

Measured memory_bytes: 3592
class UnionFind:
    # この時点でそれぞれのノードは自分を親としている
    # 初期化時に問題が0の頂点を認めるかに注意すること
    def __init__(self, n):
        self.N = n
        self.parent = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    # xの根を返す関数
    def root(self, x):
        visited_nodes = []
        while True:
            p = self.parent[x]
            if p == x:
                # 縮約
                for node in visited_nodes:
                    self.parent[node] = x
                return x
            else:
                visited_nodes.append(x)
                x = p

    # 木の結合を行う。親の配下に入る
    def unite(self, x, y):
        if not self.root(x) == self.root(y):
            if self.rank[x] > self.rank[y]:
                self.parent[self.root(y)] = self.root(x)
            else:
                self.parent[self.root(x)] = self.root(y)
                if self.rank[x] == self.rank[y]:
                    self.rank[self.root(y)] += 1

    def ifSame(self, x, y):
        return self.root(x) == self.root(y)

    # 木の根に到達すまでにたどるノードの配列を返す
    def printDebugInfo(self):
        print([self.root(i) for i in range(self.N)])


V, E = map(int, input().split())
edges = []
for _ in range(E):
    s, t, w = map(int, input().split())
    edges.append([w, s, t])
edges.sort()

tree = UnionFind(V)

weight = 0
counter = 0
for edge in edges:
    if tree.ifSame(edge[1], edge[2]):
        continue
    else:
        tree.unite(edge[1], edge[2])
        weight += edge[0]
        counter += 1
    if counter == V-1:
        break

print(weight)



Measured memory_bytes: 24776
import itertools
N, M, R = map(int, raw_input().split())
r = [int(x)-1 for x in raw_input().split()]
D = []
for i in range(N):
  D.append([200000000]*N)
  D[i][i]=0
A = [0]*M
B = [0]*M
C = [0]*M
for i in range(M):
  a, b, C[i] = map(int, raw_input().split())
  A[i] = a-1
  B[i] = b-1
  D[A[i]][B[i]] = C[i]
  D[B[i]][A[i]] = C[i]
for k in range(N):
  for i in range(N):
    for j in range(N):
      D[i][j] = min(D[i][j], D[i][k]+D[k][j])
ml = 2000000000
for p in itertools.permutations(r):
  l = 0
  for i in range(R-1):
    l += D[p[i]][p[i+1]]
  ml = min(ml, l)
print ml

Measured memory_bytes: 34664
N, M = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(M)]

G = [[] for _ in range(N)]
for x, y in L:
  x, y = x-1, y-1
  G[x].append(y)
  G[y].append(x)

for v in G[0]:
  for nv in G[v]:
    if nv == N-1:
      print("POSSIBLE")
      exit()
print("IMPOSSIBLE")

Measured memory_bytes: 79508
x, y, z, k = gets.split.map(&:to_i)

A = gets.split.map(&:to_i).sort.reverse
B = gets.split.map(&:to_i).sort.reverse
C = gets.split.map(&:to_i).sort.reverse

s = A.size * B.size
t = Array.new( s )

i = 0
A.each do |a|
  B.each do |b|
    t[i] = a + b
    i += 1
  end
end

t = t.sort.reverse[0,k]

v = []
C.each do |c|
  t.each do |u|
    v.push( c + u )
  end
end

puts v.sort.reverse[0, k]


Measured memory_bytes: 108784
#include<bits/stdc++.h>
#include<unordered_map>
/*
*▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
*    ▀▀       ▀▀▀▀▀▀    ▀     ▀▀▀▀▀▀      ▀    ▀
*   ▀  ▀      ▀         ▀     ▀            ▀  ▀
*  ▀    ▀     ▀ ▀ ▀     ▀     ▀ ▀ ▀         ▀
* ▀ ▀▀▀▀ ▀    ▀         ▀     ▀             ▀
*▀        ▀   ▀         ▀     ▀             ▀
*▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
*/
using namespace std;
void afify()
{
    ios::sync_with_stdio(0);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
#define ll long long
#define ld long double
#define mk make_pair
#define loop(i,intial,n)  for(int i=int(intial);i<n;i++)
#define loopn(j,n) for(int j=int(n);j>=0;j--)
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define all(v) v.begin(),v.end()
///////////////////////////////////////
#define SCD(a) scanf("%d",&a)
#define SCD2(a,b) scanf("%d %d",&a,&b)
#define SCLL(a) scanf("%lld",&a)
#define SCLL2(a,b) scanf("%lld %lld",&a,&b)
#define PRD(a) printf("%d\n",a)
#define PRLL(a) printf("%lld\n",a)
///////////////////////////////////////
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector <vi> vvi;
typedef vector <vll> vvll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
typedef vector<vpii> vvpii;
typedef stringstream ss;
const ll oo = (ll) 1e13;
const double EPS = 1e-4;
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
//ifstream ifs("input.txt");
//ofstream ofs("output.txt");

int main()
{
	afify();
	ll n,t;
	cin>>n>>t;
	vll v(n);
	loop(i,0,n) cin>>v[i];
	sort(all(v));
	ll res=t;
	loop(i,1,n){

		if(v[i]-v[i-1]>=t){
			res+=t;
		}
		else{
			res+=abs(v[i]-v[i-1]);
		}
	}
	cout<<res<<endl;
return 0;
}

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

int main(){
  int N; cin >> N;
  string S; cin >> S;
  
  for(int i=0; i<S.size(); i++){
    
    char now_char = S.at(i)+N;
    
    if(now_char-'A' >= 26){
      now_char -= 26;
    }
    
    cout << now_char;
    
  }
  
  return 0;

}

Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	var n int
	var s string
	fmt.Scan(&n, &s)

	var ans int
	for i := 1; i < n; i++ {
		a := map[string]int{}
		cnt := 0
		for _, c := range s[0:i] {
			a[string(c)] = 1
		}
		for _, c := range s[i:] {
			if a[string(c)] == 1 {
				cnt++
				a[string(c)]++
			}
		}
		ans = max(ans, cnt)
	}
	fmt.Println(ans)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}


Measured memory_bytes: 1944
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter

from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
#dequeを使うときはpython3を使う、pypyはダメ
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds

#mod = 10**9+7
#w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

K = int(input())
A,B = map(int, input().split())
#L = [int(input()) for i in range(N)]
#A = list(map(int, input().split()))
#S = [list(map(int, input().split())) for i in range(N)]


if A%K==0 or B%K==0:
    print('OK')
    exit()

elif A//K<B//K:
    print('OK')
    exit()
print('NG')





Measured memory_bytes: 68068
import java.util.*;
import java.util.stream.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), l = in.nextInt(); in.nextLine();
        List<String> list = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            list.add(in.nextLine());
        }
        Collections.sort(list);
        list.forEach(System.out::print);
    }
}

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

using namespace std;
using std::vector;

#define ll long long
#define vi vector<int>
#define vl vector<long long>
#define vvi vector<vi>
#define pi  pair<int,int>
#define mp  make_pair
#define pb  push_back
#define MOD int(1e9) + 7
#define PAI  3.1415926535
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define chmax(x, y) x = max(x,y)
#define chmin(x, y) x = min(x,y)
#define pr(x) cout << x << endl
#define Endl endl
#define rep(i, n) for(int i = 0 ; i < n; i++)

const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
const int ddx[8] = {-1,0,1,-1,1,-1,0,1};
const int ddy[8] = {-1,-1,-1,0,0,1,1,1};
const int inf = 99999999;
const ll linf = 1LL << 62;

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

ll lcm(ll a,ll b){
  if(a < b)swap(a , b);
  return (a / gcd(a , b)) * b;
}

int main(){
 
  int n; cin >> n;
  string s; cin >> s;
 
  vector<bool> v(26, false);

  int ans = 0;

  for(int i = 0; i < n - 1; i++){
    v[s[i] - 'a'] = true;
    vector<bool> check(26, false);
    for(int j = i + 1; j < n; j++){
      check[s[j] - 'a'] = true;
    }
    int cnt = 0;
    rep(k, 26){
      if(v[k] and check[k])
        cnt++;
    }
    chmax(ans, cnt);
  }

  pr(ans);

  return 0;
}


Measured memory_bytes: 256
#pragma warning(disable: 4996)
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <random>
#include <deque>
#include <unordered_map>
#include <functional>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <bitset>
#include <numeric>
#include <string>
#include <set>
#include <utility>
using namespace std;

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

	int n;
	cin >> n;
	bool flg = false;
	int ans = 0;
	for (int i = 1; i <= 50000; ++i) {
		if ((int)(i * 1.08) == n) {
			ans = i;
			flg = true;
			break;
		}
	}
	if (flg == true) cout << ans;
	else cout << ":(";
	return 0;
}

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

#define rep(i, N) for (int i = 0; i < (N); i++)
#define all(a) (a).begin(), (a).end()
#define pb push_back

using ll = long long;
using i_i = tuple<int, int>;

int main() {
    int N; cin >> N;
    vector<string> s(N);
    vector<int> t(N);
    rep(i, N) cin >> s[i] >> t[i];
    string s0; cin >> s0;
    int i0;
    rep(i, N) if (s[i] == s0) i0 = i;
    int T = 0;
    for (int i = i0 + 1; i < N; i++) T += t[i];
    cout << T << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=25010,K=405,mo=1e9+7;
int a[N],n,m,k;
ll dp[N][K],q[N][K],sum[N][K],q2[N][K];
ll pr[N],sf[N],ans;
ll power(ll a,ll b=mo-2){
	ll ans=1;
	while (b){
		if (b&1)ans=ans*a%mo;
		a=a*a%mo;
		b>>=1;
	}return ans;
}
ll dp0(){
	dp[1][1]=q[1][1]=k;
	if (m==1)sum[1][1]=q2[1][1]=k;
	for (int i=2;i<=n;i++){
		for (int j=k-1;j>=1;j--){
			dp[i][j]=(q[i-1][j]+dp[i-1][j-1]*(k-j+1))%mo;
			q[i][j]=(q[i][j+1]+dp[i][j])%mo;
			sum[i][j]=(q2[i-1][j]+sum[i-1][j-1]*(k-j+1)+(j>=m?dp[i][j]:0))%mo;
			q2[i][j]=(q2[i][j+1]+sum[i][j])%mo;
		}
	}
	return q2[n][1];
}
ll jc[N],ny[N];
ll ty2(ll pre,ll suf){
	for (int i=1;i<=n;i++)
		for (int j=1;j<k&&j<=i;j++){
			if (j>=pre)pr[i-pre]=(pr[i-pre]+dp[i][j])%mo;
			if (j>=suf)sf[i-suf]=(sf[i-suf]+dp[i][j])%mo;
		}
	for (int i=0;i<=n;i++)
		pr[i]=pr[i]*jc[k-pre]%mo*ny[k]%mo,
		sf[i]=sf[i]*jc[k-suf]%mo*ny[k]%mo;
	ll ans=0;
	for (int i=0;i<=n-m;i++)
		ans=(ans+pr[i]*sf[n-m-i])%mo;
	return ans;
}
int la[N];
int main(){
	cin>>n>>k>>m;
	for (int i=1;i<=m;i++)scanf("%d",&a[i]);
	int lim=25000;
	jc[0]=1;
	for (int i=1;i<=lim;i++)jc[i]=jc[i-1]*i%mo;
	ny[lim]=power(jc[lim]);
	for (int i=lim;i>=1;i--)ny[i-1]=ny[i]*i%mo;
	int las=0,tag1=0,pre=0,suf;
	for (int i=1;i<=m;i++){
		las=max(las,la[a[i]]);
		la[a[i]]=i;
		if (i-las>=k)tag1=1;
		if (!las)pre=i;
	}
	ans=power(k,n-m)*(n-m+1)%mo;
	if (tag1){
		cout<<ans<<endl;
		return 0;
	}
	ll z=dp0();
	if (!las){
		z=z*jc[k-m]%mo*ny[k]%mo;
		cout<<(ans-z+mo)%mo<<endl;
		return 0;
	}
	reverse(a+1,a+m+1);
	memset(la,0,sizeof la);
	las=0;
	for (int i=1;i<=m;i++){
		las=max(las,la[a[i]]);
		la[a[i]]=i;
		if (!las)suf=i;
	}
	z=ty2(pre,suf);
	cout<<(ans-z+mo)%mo<<endl;
}

Measured memory_bytes: 317696
def memolize(f):
    cache = {}

    def helper(x):
        if x not in cache:
            cache[x] = f(x)
        return cache[x]
    return helper

@memolize
def fib(n):
    if n == 0:
        return 1
    elif n == 1:
        return 1

    return fib(n - 1) + fib(n - 2)

n = int(input())
print(fib(n))



Measured memory_bytes: 5612
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<cmath>
#include<iomanip>
#include<functional>
using namespace std;

int INF = 1e9 + 7;

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

ll ans = INF;

ll choco(ll H, ll W) {
	ll h, w, sa, sb, sc, MAX, MIN;
	for (int i = 1; i < H; i++) {
		h = (H - i) / 2;
		sa = i * W, sb = h * W, sc = (H - i - h) * W;
		MAX = max(sa, max(sb, sc)), MIN = min(sa, min(sb, sc));
		ans = min(ans, MAX - MIN);
	}
	for (int i = 1; i < H; i++) {
		w = W / 2;
		sa = i * W, sb = (H - i)*w, sc = (H - i)* (W - w);
		MAX = max(sa, max(sb, sc)), MIN = min(sa, min(sb, sc));
		ans = min(ans, MAX - MIN);
	}
	return ans;
}

int main() {
	ll H, W;
	cin >> H >> W;
	cout << min(choco(H, W), choco(W, H)) << endl;
}

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

int main(){
    unsigned long n,k;
    cin >> n >> k;
    vector<unsigned long> h = vector<unsigned long>(n);
    for(int i=0; i<n; i++){
        unsigned long tmp;
        cin >> tmp;
        h[i] = tmp;
    }
    sort(h.begin(), h.end(), greater<unsigned long>());
    unsigned long sum = 0;
    if(k < n){
        for(int i=k; i<n; i++){
            sum += h[i];
        }
    }
    cout << sum << endl;
    
}

Measured memory_bytes: 1792
#include <iostream>
#include <string>

using namespace std;

int main(int argc, char* argv[]) {
  int N;
  cin >> N;

  string s;
  cin >> s;

  int from_west[N];
  for (int i = 0; i < N; ++i) {
    if (i == 0)
      from_west[i] = s[i] == 'E' ? 1 : 0;
    else
      from_west[i] = from_west[i - 1] + (s[i] == 'E' ? 1 : 0);
  }

  int from_east[N];
  for (int i = N - 1; i >= 0; --i) {
    if (i == N - 1)
      from_east[i] = s[i] == 'W' ? 1 : 0;
    else
      from_east[i] = from_east[i + 1] + (s[i] == 'W' ? 1 : 0);
  }

  long long ret = 0;
  for (int i = 0; i < N; ++i) {
    ret = max(ret, (long long)(from_west[i] + from_east[i] - 1));
  }

  cout << N - ret - 1 << endl;

  return 0;
}

Measured memory_bytes: 3076
# DONYOKU
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

ans = 0
for i in range(N):
    ans += min(A[i],B[i])
    B[i] -= min(A[i],B[i])
    ans += min(A[i+1],B[i])
    A[i+1] -= min(A[i+1],B[i])

print(ans)

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

#define ll long long
#define fw(p) for(int w=0;w<(p);w++)
#define fx(p) for(int x=0;x<(p);x++)
#define fy(p) for(int y=0;y<(p);y++)
#define fz(p) for(int z=0;z<(p);z++)
#define fyg(p,g) for(int y=(g);y<(p);y++)
#define fzg(p,g) for(int z=(g);z<(p);z++)
#define ce(d) cout<<d<<endl;
#define vecp(p) int aa;cin>>aa;(p).push_back(aa);
#define vecpl(p) long long aa;cin>>aa;(p).push_back(aa);
#define vecps(p) string aa;cin>>aa;(p).push_back(aa);
#define vecp2(p) cin>>aa;(p).push_back(aa);
#define vecpl2(p) long long a	b;cin>>ab;(p).push_back(ab);
#define vecps2(p) string ab;cin>>ab;(p).push_back(ab);
#define sorts(c) sort((c).begin(),(c).end());
#define reverses(c) reverse((c).begin(),(c).end());
#define vec(b) vector<int> (b);
#define vecl(b) vector<long long> (b);
#define vecs(b) vector<string> (b);
#define pb(b,a) (b).push_back((a));
#define doublece(a,b) cout<<(a)<<' '<<(b)<<endl;
#define pairs(s) vector<pair<int,int>> (s);
#define pairsp(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define MOD 1000000007
#define cey ce("Yes")
#define cen ce("No")
#define ceY ce("YES")
#define ceN ce("NO")

int main()
{
string S, T;
	cin >> S >> T;
	if (S==T.substr(0,S.size())) {
		cey;
	}
	else {
		cen;
	}
    return 0;
}



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

int main() {
    while(true) {
        string s;
        getline(cin, s);
        if (s == "END OF INPUT") return 0;
        int count = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == ' ') {
                cout << count;
                count = 0;
            } else {
                count++;
                if (i == s.size() - 1) {
                    cout << count;
                }
            }
        }
        cout << endl;
    }
}

Measured memory_bytes: 3180
N, K = map(int, input().split())
p = [(int(x)+1)/2 for x in input().split()]
cm = [0]
for n in p:
    cm.append(cm[-1]+n)
ans = 0
for n in range(N-K+1):
    ans = max(cm[n+K]-cm[n],ans)
print(ans)


Measured memory_bytes: 23588
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <tuple>
#include <algorithm>

int main() {
  int X, Y, Z, K;
  std::cin >> X >> Y >> Z >> K;

  std::vector<long long> A(X);
  std::vector<long long> B(Y);
  std::vector<long long> C(Z);

  for (int i=0; i<X; i++) std::cin >> A[i];
  for (int i=0; i<Y; i++) std::cin >> B[i];
  for (int i=0; i<Z; i++) std::cin >> C[i];

  std::sort(A.begin(), A.end(), std::greater<long long>());
  std::sort(B.begin(), B.end(), std::greater<long long>());
  std::sort(C.begin(), C.end(), std::greater<long long>());

  std::priority_queue<std::tuple<long long, int, int, int>> que;

  que.emplace(A[0]+B[0]+C[0], 0, 0, 0);

  std::unordered_set<long long> log;

  for (int n=0; n<K; n++) {
    long long ans, i, j, k;
    std::tie(ans, i, j, k) = que.top();
    que.pop();

    std::cout << ans << '\n';

    if (i+1 < X && log.count((i+1)*Y*Z + j*Z + k) == 0) {
      que.emplace(A[i+1]+B[j]+C[k], i+1, j, k);
      log.insert((i+1)*Y*Z + j*Z + k);
    }
    if (j+1 < Y && log.count(i*Y*Z + (j+1)*Z + k) == 0) {
      que.emplace(A[i]+B[j+1]+C[k], i, j+1, k);
      log.insert(i*Y*Z + (j+1)*Z + k);
    }
    if (k+1 < Z && log.count(i*Y*Z + j*Z + k+1) == 0) {
      que.emplace(A[i]+B[j]+C[k+1], i, j, k+1);
      log.insert(i*Y*Z + j*Z + k+1);
    }
  }

  return 0;
}


Measured memory_bytes: 768
import Text.Printf

secToTHS sec = (t,h,s)
    where t = sec`div`(60*60)
          h = (sec`mod`(60*60))`div`60
          s = sec - (t*60*60+h*60)

solve :: (Int,Int,Int) -> IO ()
solve (t,h,s) = do
    let (t1,h1,s1) = secToTHS (2*60*60-(t*60*60+h*60+s))
    let (t2,h2,s2) = secToTHS ((2*60*60-(t*60*60+h*60+s))*3)
    printf "%02d:%02d:%02d\n" t1 h1 s1
    printf "%02d:%02d:%02d\n" t2 h2 s2

main = do
    ss <- getContents
    mapM_ solve $ takeWhile (\x->x/=(-1,-1,-1)) $ map (\x->((x!!0),(x!!1),(x!!2))) $ map (\x->map (\y->read y::Int) $ words x) $ lines ss

Measured memory_bytes: 3972
// ConsoleApplication2.cpp : This file contains the 'main' function. Program execution begins and ends there.
//


#include <iostream>
#include <string>
using namespace std;
int main(){
   int h,w;
   cin>>h>>w; string s;
   for(int i=0;i<w+2;i++){
       cout<<"#";
   }
   cout<<endl;
   for(int i=0;i<h;i++){
       cout<<"#";
       cin>>s;
       cout<<s<<"#"<<endl;
   }
   for(int i=0;i<w+2;i++){
       cout<<"#";
   }
    return 0;
}




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

//temmplate------
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define INF 1e9
#define ZERO(a) memset(a, 0, sizeof(a))
typedef long long lint;
//------template

int main(){
    int N,M;
    cin >> N >> M;
    if (M == N){
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
}

Measured memory_bytes: 256