akhauriyash/Code-Regression huggingface dataset:
//#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast,no-stack-protector") 
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
/*#include <x86intrin.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T> using ordered_set = tree<T, null_type, std::less<T>, rb_tree_tag, tree_order_statistics_node_update>;*/
#define ll long long
#define ull unsigned long long
#define int long long
#define ld long double
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define repb(i, r, l) for (int i = r; i >= l; i--)
#define sz(a) (int)a.size()
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define ret(a) {cout << a; exit(0);}

using namespace std;

mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b,ll mod) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
                                                                    
typedef pair < int , int > pii ;
typedef pair < long long  , long long > pll ;

const int N = 2e5 + 5;
int n ;
string s;
int a[N] , cnt[N];
vector < int > v[N];
int get(int x ,int y){
	if(x == y)return (x * y);
	if(x == 3 and y == 2)	
		return 3 * 4;
    if(y == 1)return x;
    assert(0);
}
int f(int x){
	if(x == 0)return 1;
	return x * f(x - 1);
}
int C(int n , int k){
	if(k == 1)return 3;
	if(k == 2)return 6;
	return 6;
}
main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n;
	ll res = 1;
	rep(i , 1, n)
    	cin >> a[i] , v[a[i]].pb(i);
	rep(i , 0 , n-2){
		if(sz(v[i]) > 3)ret(0);
		if(sz(v[i + 1]) > sz(v[i]))ret(0);
		int Sz = sz(v[i]) + sz(v[i + 1]);
		vector < pii > edge;
		bool was[Sz+Sz];
		for(int i = 0 ; i <= Sz;i++)
			was[i] = 0;
		for(int j = 0 ; j < sz(v[i]); j++)
			for(int k = 0 ; k  < sz(v[i + 1]); k++)
				if(v[i][j] < v[i + 1][k])
					edge.pb({j+1 , sz(v[i]) + k + 1});
		int cur = 0;
		for(int mask = 0 ; mask < (1 << sz(edge)) ; mask++){
			bool ok = 1;
			int cnt = 0;
			for(int i = 0 ; i < sz(edge); i++){
				 if(mask&(1 << i)){
				 	if(was[edge[i].fi] or was[edge[i].se]){
				 		ok = 0 ;break;
				 	}
				 	was[edge[i].fi] = was[edge[i].se] = 1;	
				 	cnt++;
				 }
			}
			if(cnt == sz(v[i + 1]) and ok)
				cur++;				
			for(int i = 0 ; i <= Sz;i++)
				was[i] = 0;
        }
        res *= cur;
        res %= mod;			
	}
	cerr << res << ' ' << sz(v[0]) << ' ';
	cerr << C(3 , sz(v[0])) << ' ';
	
	cout << C(3 , sz(v[0])) * res % mod;	
}

Measured memory_bytes: 10368
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <map>
using namespace std;

typedef long long ll;
typedef double lf;
typedef long double Lf;
typedef pair <int,int> pii;
typedef pair <ll, ll> pll;

#define TRACE(x) cerr << #x << "  " << x << endl
#define FOR(i, a, b) for (int i = (a); i < int(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define _ << " " <<

#define fi first
#define sec second
#define mp make_pair

const int MAXN = 100100;

int n, p[MAXN];

int start(int x) {
	int ret = 1;
	if (x == n - 1) return ret;

	while (x + 1 < n && p[x] == p[x + 1]) {
		ret++;
		x++;
	}

	if (x == n - 1) return ret;

	bool kamo = (p[x] < p[x + 1]);

	while (x + 1 < n && ((p[x] < p[x + 1]) == kamo || p[x] == p[x + 1])) {
		ret++;
		x++;
	}

	return ret;
}

int main() {
	scanf("%d",&n);
	REP(i, n) scanf("%d",&p[i]);
	
	int sol = 0;
	REP(i, n) {
		sol++;
		i += start(i) - 1;
	}

	printf("%d\n",sol);
	return 0;
}

Measured memory_bytes: 640
#include<stdio.h>
#include<string.h>
#define N 12
#define M 1000000
char hash[M][N];

int getChar(char t){
  if (t=='A')return 1;
  else if(t=='C')return 2;
  else if(t=='G')return 3;
  else if(t=='T')return 4;
  else return 0;
}


int getint(char str[]){
  int sum=0,i,a=1;
  for (i=0;i<strlen(str);i++){
    sum+=a*(getChar(str[i]));
    a*=5;
  }
  return sum;
}

int h1(int key){
    return key%M;
}
int h2(int key){
    return 1+(key%(M-1));
}
int h(int key,int i){
    return (h1(key)+i*h2(key))%M;
}

void insert(char t[]){
    int i=0,v,j;
    v=getint(t);
    while(1){
        j=h(v,i);
        if(strcmp(hash[j],t)==0)break;
        else if(strlen(hash[j])==0){
            strcpy(hash[j],t);
            break;
        }
        else i++;
    }
}

int search(char t[]){
    int i=0,v,j;
    v=getint(t);
    while(1){
        j=h(v,i);
        if(strcmp(hash[j],t)==0)return 1;
        else if(strlen(hash[j])==0||i>=M)return 0;
        else i++;
    }

}

int main(){
    int i,n,a[N];
    char s[N],t[N];

    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%s %s",s,t);
        if(s[0]=='i')insert(t);
        else {
            if(search(t)==0)printf("no\n");
            else printf("yes\n");
        }
    }
  
    return 0;
}



Measured memory_bytes: 13388
class UnionFind():
    def __init__(self, N):
        self.N = N
        self.rank = [0] * N
        self.par = [i for i in range(N)]
        self.counter = [1] * N

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            z = self.counter[x] + self.counter[y]
            self.counter[x], self.counter[y] = z, z
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def size(self, x):
        x = self.find(x)
        return self.counter[x]

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

    def groups(self):
        group = set()
        for i in range(self.N):
            group.add(self.find(i))
        return len(group)


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

if N == 2:
    print(1)
    quit()


graph = UnionFind(N)
for i in range(M):
    x, y, z = map(int, input().split())
    graph.unite(x-1, y-1)

ans = graph.groups()
print(ans)

Measured memory_bytes: 17576
import os

def main():
    count = int(input())
    list_num = list(map(int, input().split()))
    result_list = []
    if not(1 in list_num):
        print("-1")
    else:
        num = 1
        for i in list_num:
            if num == i:
                result_list.append(num)
                num += 1
        print(len(list_num) - len(result_list))


if __name__ == "__main__":
    main()



Measured memory_bytes: 24744
#include<iostream>
#include<algorithm>
#include<math.h>
#include<cstdio>
#include<ctype.h>
#include<stdio.h>
#include<set>
#include<vector>
#include<map>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include <numeric>
typedef long long ll;
using namespace std;

ll gcd(ll a, ll b){
if(a<b){return gcd(b,a);}
else if(a%b){return gcd(b,a%b);}
else{return b;}
}

int main(){
string s;
cin>>s;
string ans;
for(int i=0; i<s.size(); i+=2){
ans+=s[i];
}
cout<<ans<<endl;
}


Measured memory_bytes: 512
#define _CRT_SECURE_NO_WARNINGS
/*                   وتزودوا فإن خير الزاد التقوى                    */
/*       وما تدري نفس ماذا تکسب غدا وما تدري نفس باي ارض تموت      */
#include <bits/stdc++.h>
#include<unordered_map>
#include<iomanip>
#include<fstream>
using namespace std;
#include<iostream>
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define dll double
#define PI acos(-1)
#define watch(x) cout<<#x<<" = { "<<x<<" }\n"
#define sz(n) n.size()
#define M_Sayed fast() 
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define RT(v) return cout<<v,0
int dx[] = { 0, 1, 0, -1, 1, 1, -1, -1 };
int dy[] = { 1, 0, -1, 0, 1, -1, 1, -1 };
const double EPS = (1e-7);
ll Ceil(ll x, ll y) { return (x + y - 1) / y; }
//void run() {
//#ifndef ONLINE_JUDGE
//	freopen("input.txt", "r", stdin);
//	//freopen("output.txt", "w", stdout);
//#else
//#endif
//}
ll gcd(ll a, ll b) { return !b ? abs(a) : gcd(b, a % b); }
ll lcm(ll a, ll b) { return abs(a / gcd(a, b)) * b; }
ll power(ll x, ll y, ll mod) {
	if (y == 0) return 1;
	if (y == 1) return x % mod;
	ll r = power(x, y >> 1, mod);
	return (((r * r) % mod) * power(x, y & 1, mod)) % mod;
}
void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }
ll n, m, w;
ll vis[111][100099];
vector<ll>v, v2;
ll knapsak(ll x, ll pr)
{
	if (pr==0)
		return 0;
	if (x == n)return 2e9;
	ll ret = 2e9;
	if (vis[x][pr])
		return vis[x][pr];
	if (pr >= v2[x]) {
		ret = knapsak(x + 1, pr - v2[x])+v[x];
	}
	ret = min(ret, knapsak(x + 1,  pr));
	vis[x][pr] = ret;
	return ret;
}
int main()
{
	//run();
	M_Sayed;
	cin >> n >> w;
	v.resize(n);
	v2.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i] >> v2[i];
	}
	for (int i = 1e5; i >= 0; i--)
	{
		if (knapsak(0, i) <= w)RT(i);
	}
}

Measured memory_bytes: 80000
#include<bits/stdc++.h>
#define sz 100002
#define pb push_back
#define ff first
#define ss second
#define ll long long
#define P push
#define VEC(n) ll int x; vector<ll int>v;for(int i=0;i<n;i++){cin>>x;v.pb(x);}
#define TEST() int test;cin>>test; while(test--)
#define FAST() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;

//ll int LCM(ll int a,ll int b) { ll int gcd=__gcd(a,b);ll int lcm=a*b/gcd;return lcm;}
//ll int bigmod(ll int b, ll int p, ll int m){if(p==0)return 1;if(p%2!=0) return b%m*fun(b,p-1,m)%m;if(p%2==0){ ll int res=fun(b,p/2,m);return (res%m*res%m)%m;}}
//void seive() { prime[np++]=2;for(i=3; i<=sz; i+=2){if(mark[i]==0){ prime[np++]=i;for(j=i*i; j<=sz; j+=i) mark[j]=1; } }}
//string add(string s1,string s2) {string s;int j=s1.size()-1,c=0,m; for(int i=s2.size()-1; i>=0; i--) {if(j>=0)m=s2[i]-'0'+s1[j]-'0'+c;else m=s2[i]-'0'+c; if(m>9) { s+=m%10+'0';c=m/10; } else {  c=0;s+=m+'0'; }j--; } if(c!=0) {s+=c+'0'; }reverse(s.begin(),s.end());return s;}
//int pos;string mul(int n) {string s;for(int i=0; i<pos; i++) { s+="0"; }pos++;int c=0,m; for(int i=s1.size()-1; i>=0; i--) { m=(s1[i]-'0')*n+c;if(m>9) { s+=m%10+'0';c=m/10;} else { c=0; s+=m+'0';} }while(c!=0) { s+=c%10+'0';c=c/10;}    reverse(s.begin(),s.end());return s;}

int main()
{
    FAST();
    ll int n,m;
    cin>>n;
    map<string,int>mp;
    string s;
    while(n--)
    {
        cin>>s;
        mp[s]++;
    }
    cout<<"AC x "<<mp["AC"]<<endl;
    cout<<"WA x "<<mp["WA"]<<endl;
    cout<<"TLE x "<<mp["TLE"]<<endl;
    cout<<"RE x "<<mp["RE"]<<endl;


}



Measured memory_bytes: 3656
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,x;
	long long sum=0;
	scanf("%d",&n);
	int f=0,mn=1e9+1;
	for(int i=0;i<n;i++){
		scanf("%d",&x);
		if(x<0)
			f++;
		sum+=abs(x);
		mn=min(mn,abs(x));
	}
	if(f%2==1)
		sum-=2*mn;
	printf("%lld\n",sum);
} 

Measured memory_bytes: 256
#include "iostream"
#include "vector"
#include "string"
#include "algorithm"
#include "math.h"
#include "cstring"
#include "stack"
#include "queue"

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<vector<ll> > mat;

//最大公約数
int gcd(int a, int b)
{
  while (b != 0)
  {
    int i = a % b;
    a = b;
    b = i;
  }
  return a;
}

int main()
{
  int n;
  cin >> n;
  int a[100100];
  for (int i = 0; i < n; i++)
  {
    cin >> a[i];
  }

  int lgcd[100100], rgcd[100100];
  lgcd[0] = a[0];
  rgcd[n - 1] = a[n - 1];
  for (int i = 1; i < n - 1; i++)
  {
    lgcd[i] = gcd(lgcd[i - 1], a[i]);
  }
  for (int i = n - 2; i > 0; i--)
  {
    rgcd[i] = gcd(rgcd[i + 1], a[i]);
  }

  int ans = max(lgcd[n - 2], rgcd[1]);
  for (int i = 1; i < n - 1; i++)
  {
    ans = max(ans, gcd(lgcd[i - 1], rgcd[i + 1]));
  }
  cout << ans << "\n";
}

Measured memory_bytes: 1408
// 基本テンプレート (縮小版)

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define int long long
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
typedef pair<int, int> pii;
typedef long long ll;
constexpr ll INF = 1001001001001001LL;
constexpr ll MOD = 1000000007LL;

int N, a[200010];

signed main() {
    cin >> N;
    rep(i,0,N) cin >> a[i];

    deque<int> ans;
    rep(i,0,N) {
        if(N % 2) {
            if(i % 2) ans.push_back(a[i]);
            else ans.push_front(a[i]);
        }
        else {
            if(i % 2) ans.push_front(a[i]);
            else ans.push_back(a[i]);
        }
    }
    rep(i,0,N) {
        if(i == 0) printf("%lld", ans[i]);
        else printf(" %lld", ans[i]);
    }
    cout << endl;
    return 0;
}

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

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

    if(A.at(0) == B.at(2) && A.at(1) == B.at(1) && A.at(2) == B.at(0)){
        cout << "YES" << endl;
    }
    else{
        cout << "NO" << endl;
    }
}

Measured memory_bytes: 3596
/*author: hyperion_1724
  date: 
*/
#include <bits/stdc++.h>
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	

	long long r,D,x;
	cin>>r>>D>>x;
	for (long long i = 0; i < 10; ++i)
	{
		x=r*x-D;
		cout<<x<<endl;
	}
	

	return 0;
}

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

#define REP(i, s, e) for(int i = (int)s; i < (int) e; i++)
#define rep(i, n) REP(i, 0 ,n)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define fi first
#define se second
#define pb push_back
#define mp nake_pair

typedef long long ll;

struct Edge{
    int to, cost;
    Edge(){};
    Edge(int to, int cost):to(to), cost(cost){};
};

struct Tree{
    int n;
    vector<vector<Edge>> es;
    vector<int> r, flag1, flag2;
    Tree(int n_):n(n_), es(n_), r(n_, 1e9), flag1(n_), flag2(n_) {};
    void add_edge(int from, int to, int cost){
        es[from].pb({to, cost});
        es[to].pb({from, cost});
    }
    void calcR(int k, int v){
        if(r[k] != 1e9) return;
        r[k] = v;
        for(auto&e:es[k]) calcR(e.to, v+1);
    }
    void setFlag(int k) {
        flag1[k] = flag2[k] = 1;
    }
    int check(int k){
        for(auto & e :es[k]) if(r[k] < r[e.to]) flag1[k] |= check(e.to);
        return flag1[k];
    }
    int dfs(int k){
        if(flag1[k] == 0) return 0;
        int ret = 0;
        for(auto& e :es[k]) if(r[k]<r[e.to]) ret += min(e.cost, flag2[e.to] == 0 ? dfs(e.to) : (int)1e6);
        return ret==0?1e6:ret;
    }
};

int main(){
    int n;
    cin>>n;
    Tree t(n);
    rep(i, n-1){
        int c;
        cin>>c;
        if(c > 0) t.setFlag(i+1);
    }
    rep(i, n - 1){
        int u, v, p;
        cin>>u>>v>>p;
        t.add_edge(u, v, p);
    }
    t.calcR(0, 0);
    t.check(0);
    cout<<t.dfs(0)<<endl;
}

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
ll ans = 0;
bool cmp(const vector<ll> &a, const vector<ll> &b){
  return a[1] < b[1]; //>なら降順 
}
bool cmp2(const vector<ll> &a, const vector<ll> &b){
  return a[1] > b[1]; //>なら降順 
}
int main()
{
ll t ;
cin >> t ;
rep(i,t){
  ans=0;
  ll n ;
  cin >> n ;
  vector<vector<ll>> v(0, vector<ll>(2,0) );
  vector<vector<ll>> vv(0, vector<ll>(2,0) );
  rep(i,n){
    ll a , b , c ;
    cin >> a >> b >> c ;
    a--;
    if(b>=c){
      v.push_back(vector<ll>(2,0));
      v[v.size()-1][0]=b-c;
      v[v.size()-1][1]=a;
      ans+=c;
    }
    else if(a+1!=n){
      vv.push_back(vector<ll>(2,0));
      vv[vv.size()-1][0]=c-b;
      vv[vv.size()-1][1]=a+1;
      ans+=b;
    }
    else ans+=b;
  }
  sort(v.begin(),v.end(),cmp);
  ll itr=0;
  priority_queue< ll, vector<ll>, greater<ll> > q;
  rep(i,n){
    while(itr<v.size()&&v[itr][1]==i){
      q.push(v[itr][0]);
      itr++;
    }
    while(q.size()>i+1)q.pop();
  } 
  while(!q.empty()){
    ans+=q.top();
    q.pop();
  }
  sort(vv.begin(),vv.end(),cmp2);
  itr=0;
  rep(i,n){
    while(itr<vv.size()&&vv[itr][1]==n-1-i){
      q.push(vv[itr][0]);
      itr++;
    }
    while(q.size()>i+1)q.pop();
  } 
  while(!q.empty()){
    ans+=q.top();
    q.pop();
  }
  cout << ans << endl;
}
return 0;
}

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

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

  rep(i, n) {
    cin >> ls[i];
  }

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

  int sum = 0;
  rep(i, n-1) {
    sum += ls[i];
  }

  cout << sum + ls[n-1]/2 << endl;
}

Measured memory_bytes: 256
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define ll long long int
#define ld long double
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define all(x) x.begin(),x.end()
#define F first
#define S second
#define fo(i,n) for(int i=0;i<(n);i++)
#define inp(a) int a;cin>>a;
#define inpa(a,n)vector<int> a(n);fo(i,n)cin>>a[i];
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
using namespace std;
#define int ll
// #define MAX 20
#define INF (int)1e18

template<class T> ostream& operator<<(ostream& cout,vector<T> V)
{cout<<"[ ";for(auto v:V)cout<<v<<' ';return cout<<']';}
template<class L,class R> ostream& operator<<(ostream& cout,pair<L, R> P)
{return cout<<'('<<P.F<<','<< P.S<<')';}

vector<int> sieve(int n)
{
	bool prime[n+1]={0};
	for(int i=2;i<=n/i;i++)
	{
		if(!prime[i])
		{
			for(int j=i*i;j<=n;j+=i)
			{
				prime[j]=1;
			}
		}
	}
	vector<int> p;
	for(int i=2;i<=n;i++)
		if(!prime[i])
			p.pb(i);
	return p;
}


int f(int x)
{
	int ans=0;
	for(int i=0;;i++)
	{
		if(x-i<0)
		{
			return i-1;
		}
		x-=i;
	}
}

signed main()
{
	fio
	vector<int> p=sieve(1e6+5);
	inp(n)
	vector<int> fac;
	for(int i=0;i<p.size() && p[i]*p[i]<=n;i++)
	{
		if(n%p[i]==0)
		{
			fac.pb(0);
			while(n%p[i]==0)
			{
				fac.back()++;
				n/=p[i];
			}
		}
	}
	if(n!=1)
		fac.pb(1);
	int ans=0;
	for(int i:fac)
		ans+=f(i);
	cout<<ans<<'\n';
	printclock;
}

Measured memory_bytes: 5196
#include <iostream>
#include <climits>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

#define pb push_back

int main(void){
	string s, t;
	cin >> s >> t;
	const int n = s.size();
	const int m = t.size();
	vector<vector<int> > dp(n+1, vector<int>(m+1, -1));
	for(int i = 0;i <= n;i++)
		dp[i][0] = 0;
	for(int i = 0;i <= m;i++)
		dp[0][i] = 0;
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
			if(s[i-1] == t[j-1]){
				dp[i][j] = dp[i-1][j-1] + 1;
			}
			else{
				dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
			}

		}
	}
	vector<char> ans;
	for(int i = n, j = m;i != 0 && j != 0;){
		if(s[i-1] == t[j-1]){
			ans.pb(s[i-1]);
			i--; j--;
		}
		else if(dp[i][j-1] < dp[i-1][j]){
			i--;
		}
		else
			j--;
	}
	reverse(ans.begin(), ans.end());
	string final(ans.begin(), ans.end());
	cout << final << endl;
	return 0;
}

Measured memory_bytes: 35584
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
typedef vector<int> VI;
ll mm=1000000000;ll MM=mm+7;
#define rep(i, n) for(int i=0;i<n;i++)
#define PI 3.141592653589793

int main(){
    int a,b,c;
    cin >> a >> b >> c;
    
    bool d=false;
    if(a==5 && b==5 && c==7)d=true;
    if(a==5 && c==5 && b==7)d=true;
    if(b==5 && c==5 && a==7)d=true;
    if(d)cout << "YES" << endl;
    else cout << "NO" << endl;

}

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

namespace Atc_0006
{
    class Program
    {
        static void Main(string[] args)
        {
            int deg = int.Parse(Console.ReadLine());

            if (30 <= deg)
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
        }
    }
}


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

using namespace std;

typedef long long ll;
const ll INF = 1LL<<60;

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

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

ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}

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

  ll N;
  cin >> N;

  if(N % 2 == 0){
    ll ans = 0;
    ans += N / 10;
    N = N / 10;
    
    ll d5 = 5;
    while(N >= d5){
      ans += N / d5;
      d5 = d5 * 5;
    }

    cout << ans << endl;
    
  }else{
    cout << 0 << endl;
  }

  return 0;
}


Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author yosiiii
 */


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

class CWalkOnMultiplicationTable {
public:
	void solve(std::istream& in, std::ostream& out) {
        ll n;
        in >> n;
        ll ans=n-1;
        for(ll i=1;i<=sqrt(n);i++){
            if(n%i==0){
                ans=min(ans,i-1+(n/i)-1);
            }
        }
        out <<ans << endl;
	}
};


int main() {
	CWalkOnMultiplicationTable solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


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

const int sz = 10000040;
bool p[sz];

int main() {
	for(int i = 0; i < sz; i++)
		p[i] = true;

	p[0] = p[1] = false;
	for(int i = 0; i*i <= sz; i++) {
		if(p[i]) {
			for(int j = i*2; j <= sz; j += i) {
				p[j] = false;
			}
		}
	}

	int n;
	while(cin >> n, n) {
		for(int i = n; i > 0; i--) {
			if(p[i] && p[i-2] && p[i-6] && p[i-8]) {
				cout << i << endl;
				break;
			}
		}
	}
}

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

int main() {
	int N;
	cin >> N;
	vector<int> h(N);
	vector<int> o(N);
	for (int i = 0; i < N; ++i)cin >> h.at(i);
	int count = 0;
	while (true) {
		if (h == o)break;
		int i = 0;
		while (i < N) {
			if (h.at(i) == 0)++i;
			else {
				++count;
				while (i < N && h.at(i) > 0) {
					h.at(i)--;
					++i;
				}
			}
		}
	}
	cout << count << endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep_(i, n, m) for (int i = n; i < (int)(m); i++)
#define all(v) v.begin(), v.end()
#define int long long
#define stoi stoll
//#define _GLIBCXX_DEBUG

signed main() {
  int N; cin >> N;
  string S; cin >> S;
  
  vector<int> s(0);
  int k = 1;
  rep(i, N-1) {
    if(S[i] == S[i+1]) k++;
    else {
      s.push_back(k);
      k = 1;
    }
  }
  s.push_back(k);
  
  if(s.size() == 1) {
    cout << 0 << endl;
    return 0;
  }
  
  
  
  int ans = 0;
  int a = 0;
  if(S[0] == '#') {
    for(int i=1; i<(int)(s.size()); i+=2) a += s[i];
    ans = a;
    s.push_back(0);
    for(int i=1; i<(int)(s.size()); i+=2) {
      ans = min(ans, a + s[i-1] - s[i]);
      a = a + s[i-1] - s[i];
    }
    cout << ans << endl;
  } else {
    if(s.size() == 2) {
      cout << 0 << endl;
      return 0;
    }
    for(int i=0; i<(int)(s.size()); i+=2) a += s[i];
    ans = a;
    s.push_back(0);
    for(int i=1; i<(int)(s.size()); i+=2) {
      //cout << ans << endl;
      ans = min(ans, a - s[i-1]);
      a = a - s[i-1] + s[i];
    }
    cout << ans << endl;
  }

}

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

class UnionFind
{
private:
	vector<int> d;

public:
	UnionFind(int n = 0) :d(n, -1) {}

	int Find(int x)
	{
		if (d[x] < 0) return x;
		return d[x] = Find(d[x]);
	}

	bool Unite(int x, int y)
	{
		x = Find(x);
		y = Find(y);
		if (x == y) return false;
		if (d[y] < d[x]) swap(x, y);
		d[x] += d[y];
		d[y] = x;
		return true;
	}

	bool Same(int x, int y) { return Find(x) == Find(y); }

	int Size(int x) { return -d[Find(x)]; }
};

int main()
{
	int n, m, k;
	cin >> n >> m >> k;
	UnionFind uf(n);

	vector<int> f(n);
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		f[a]++;
		f[b]++;
		uf.Unite(a, b);
	}

	vector<vector<int>> b(n);
	for (int i = 0; i < k; i++) {
		int c, d;
		cin >> c >> d;
		--c; --d;
		b[c].push_back(d);
		b[d].push_back(c);
	}

	for (int i = 0; i < n; i++) {
		int ans = uf.Size(i) - 1 - f[i];
		for (const auto& item : b[i]) {
			if (uf.Same(i, item)) ans--;
		}
		printf("%d%c", ans, i == n - 1 ? '\n' : ' ');
	}
}


Measured memory_bytes: 6784
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define endl "\n"

int main()
{
  i64 K;
  string S;
  cin >> K >> S;
  if (S.size() <= K)
    cout << S << endl;
  else
    cout << S.substr(0, K) << "..." << endl;
  return 0;
}


Measured memory_bytes: 3632
using System;
using System.Linq;

class Program {
    static void Main(string[] args) {
        string s = cin.next();
        s = cin.next();
        Console.WriteLine("A{0}C", s[0]);
    }
}


public class cin {
    private static string[] s = new string[0];
    private static int i = 0;

    private static char[] cs = new char[] { ' ' };

    public static string next() {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        i = 0;
        return next();
    }

    public static int ni() {
        return int.Parse(next());
    }

    public static long nextLong() {
        return long.Parse(next());
    }

    public static double nextDouble() {
        return double.Parse(next());
    }

}


Measured memory_bytes: 2648
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <iomanip>
#include <algorithm>
#include <sstream>
#include <string>
#include <math.h>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
const int mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    char a, b;
    cin >> a >> b;
	if (a > b) cout << ">";
	else if (a < b) cout << "<";
	else cout << "="; 
}

Measured memory_bytes: 3644
def checkPalindrome(a,b):
    count=0
    for i in range(100,1000):
        p1=str(i//10)
        p2=str(i%10)
        p3=int(p1+p2+p1[1]+p1[0])
        if b>=p3 and p3>=a:
            count+=1
    return count


a,b=map(int,input().split())
print(checkPalindrome(a,b))


Measured memory_bytes: 2940
#include<iostream>
using namespace std;
int main(){
	int k,s;
	cin >> k >> s;
	int ans=0;
	for(int i=0;i<=k;i++){
		for(int j=0;j<=k;j++){
			if(i+j<=s && i+j>=s-k) ans++;
		}
	}
	cout << ans << endl;
}


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

bool prime(int n) {
	for (int i = 2; i <= sqrt(n); i++) {
		if (n % i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}

signed main() {
	int n, m, ans = 0;
	cin >> n >> m;
	vector<int>s[14];
	rep(i, m) {
		int k;
		cin >> k;
		rep(j, k) {
			int a;
			cin >> a;
			s[a - 1].push_back(i);
		}
	}
	int p[14];
	rep(i, m) {
		cin >> p[i];
	}
	for (int i = 0; i < (1 << n); i++) {
		int bit[114];
		rep(j, n) {
			bit[j] = i / (1 << j) % 2;
		}
		int cnt[14];
		fill(cnt, cnt + 12, 0);
		rep(j, n) {
			if (bit[j] == 1) {
				rep(k, s[j].size()) {
					cnt[s[j][k]]++;
				}
			}
		}
		bool bou = true;
		rep(i, m) {
			if (cnt[i] % 2 != p[i]) {
				bou = false;
			}
		}
		if (bou) {
			ans++;
		}
	}
	cout << ans << endl;

	return 0;
}


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

int main() {
	int ls, rs;
	int a, b, c;
	bool j = true;
	cin >> a >> b >> c;
	ls = a - b;
	rs = b - c;
	cin >> a >> b >> c;
	if (ls != a - b) {
		j = false;
	}
	if (rs != b - c) {
		j = false;
	}
	cin >> a >> b >> c;
	if (ls != a - b) {
		j = false;
	}
	if (rs != b - c) {
		j = false;
	}
	if (j)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

int dsum(int n) {
    int sum = 0;
    while (n > 0) {
        sum += (n % 10);
        n = n / 10;
    }
    return sum;
}

int main() {
    int N;
    cin >> N;
    int s = dsum(N);
    if (N % s == 0) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(begin, i, end) for (int i = begin; i < (int)(end); i++)
#define all(v) v.begin(), v.end()
const int MOD = 1000000007;

int main()
{
    int N, M;
    cin >> N >> M;
    vector<int> A(N);
    int sum = 0;
    rep(0, i, N)
    {
        cin >> A[i];
        sum += A[i];
    }
    int count;

    rep(0, i, N)
    {
        if (sum > 4 * M * A[i])
        {
            continue;
        }
        count++;
    }
    if (count < M)
    {
        cout << "No" << endl;
    }
    else
    {
        cout << "Yes";
    }
}

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

int main()
{
  int k,l,card[4][13];
  char c;

  for(int i=0;i<4;i++)
    {
      for(int j=1;j<14;j++)
        {
          card[i][j]=0;
        }
    }
  cin >> k;
  for(int i=0;i<k;i++)
    {
      cin >> c >> l;
      if(c=='S') card[0][l]=N;
      if(c=='H') card[1][l]=N;
      if(c=='C') card[2][l]=N;
      if(c=='D') card[3][l]=N;
    }

  for(int i=0;i<4;i++)
    {
      for(int j=1;j<14;j++)
        {
          if(card[i][j]==0)
            {
              if(i==0) cout << 'S' << ' ' << j <<endl;
              else if(i==1)    cout << 'H' << ' ' << j <<endl;
              else if(i==2)    cout << 'C' << ' ' << j <<endl;
              else if(i==3)    cout << 'D' << ' ' << j <<endl;
            }
        }
    }
  return 0;
}

Measured memory_bytes: 3120
#include <stdio.h>
#define MAX 8
#define Y 1
#define N -1

int A[MAX][MAX],c[MAX],b[MAX],d[2*MAX-1],e[2*MAX-1];

void full(){
  int i,j;
  for(i=0;i<MAX;i++){
    d[i]=c[i]=N;
  }
  for(i=0;i<2*MAX-1;i++){
    d[i]=e[i]=N;
  }
}

  void Bord(){
    int i,j;
    for(i=0;i<MAX;i++){
      for(j=0;j<MAX;j++){
	if(A[i][j]==1){
	  if(b[i]!=j)
	    return;
	}
      }
    }

    for(i=0;i<MAX;i++){
      for(j=0;j<MAX;j++){
	if(b[i]==j){
	  printf("Q");
	}
	else{
	  printf(".");
	}
      }
	printf("\n");
      }
    }

    void Que(int i){
      int j;
      if(i==MAX){
	Bord();
	return;
      }
      for(j=0;j<MAX;j++){
	if(c[j]==Y||d[i+j]==Y||e[i-j+MAX-1]==Y)
	  continue;
	b[i]=j;
	c[j]=d[i+j]=e[i-j+MAX-1]=Y;
	Que(i+1);
	c[j]=d[i+j]=e[i-j+MAX-1]=N;
      }
    }

    int main(){
      int i,j,n,k,w;
      full();
      for(i=0;i<MAX;i++){
	for(j=0;j<MAX;j++){
	  A[i][j]=0;
	}
      }
      scanf("%d",&n);
      i=0;
      while(i<n){
	scanf("%d%d",&k,&w);
	A[k][w]=1;
	i++;
      }
      Que(0);
      return 0;
    }



Measured memory_bytes: 2108
function main(input) {
   input = input.trim();
  const a = input.split(" ").map(Number);
  const g = [0, 1, 3, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1];
 console.log(g[a[0]]==g[a[1]]?"Yes":"No");
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 29656
#include <bits/stdc++.h>
using namespace std;
#define dump(x) cout << (x) << '\n';
typedef int64_t Int;
Int mod = 1e9+7;
Int INF = 1e9+7;

int main() {
    ios::sync_with_stdio(false);
    Int n;
    string s;
    cin >> n >> s;
    map<char, Int> mp;
    for (Int i = 0; i < n; i++) mp[s[i]]++;
    Int res = 1;
    for (auto itr = mp.begin(); itr != mp.end(); itr++) {
        res *= itr->second + 1;
        res %= mod;
    }
    dump(res - 1);
    return 0;
} 

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

#define REP(i,num) for(int i=0;i<(num);++i)
#define LOOP(i) while(i--)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto pitr=c.begin();pitr!=c.end();++pitr){cout<<*pitr;if(next(pitr,1)!=c.end())cout<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

vector<ll> enum_div(ll n){
	vector<ll> ret;
	for(ll i=1;i*i<=n;++i){
		if(n%i==0){
			ret.push_back(i);
			if(i*i!=n){
				ret.push_back(n/i);
			}
		}
	}
	return ret;
}

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

	ll N=in(),M=in();
	auto D=enum_div(M);
	sort(ALL(D));

	ll A=0;
	for(auto& x:D){
		if(x*N<=M) A=x;
	}
	
	out(A);
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, a, n) for (int i = n - 1; i >= a; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

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

  int n, k;
  cin >> n >> k;
  cout << ((n - 1) + (k - 2)) / (k - 1) << endl;
}


Measured memory_bytes: 3564
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
alp = "abcdefghijklmnopqrstuvwxyz"

def Mo(n,q,c,qi,base):
    ans = [0]*q
    ln = [-1]*(n+1)

    #BITの構成
    BIT = [0]*(n+1)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum
    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    #Rが小さい方から見ていく,BITによる累積和の処理を含む
    pr = 0
    for ist in qi:
        i = ist%(base)
        l = (ist//(base))%(base)
        r = ist//(base)**2
        for j in range(pr,r):
            cj = c[j]
            ij = ln[cj]
            if ij != -1:
                BIT_update(ij,-1)
            ln[cj] = j+1
            BIT_update(j+1,1)
        pr = r
        ans[i] = BIT_query(r)-BIT_query(l-1)
    return ans

def main():
    n,q = map(int,ipt().split())
    c = [int(i) for i in ipt().split()]
    qi = []
    base = 10**6+1
    for i in range(q):
        l,r = map(int,ipt().split())
        qi.append(r*(base**2)+l*base+i)
    qi.sort()

    ans = Mo(n,q,c,qi,10**6+1)

    for i in ans:
        print(i)

    return None

if __name__ == '__main__':

    main()


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

using namespace std;

int main(){
	int N;
	while(cin >> N){
		vector<int> a(N);
		for(int i=0;i<N;i++) cin >> a[i];
		long long res = (1LL<<60);
		for(int i=0;i<2;i++){
			int sgn = (i ==0 ? 1 : -1);
			long long op = 0;
			long long sum = 0;
			for(int j=0;j<N;j++){
				sum += a[j];
				if(sgn == 1 && sum <= 0){
					op += 1 - sum;
					sum = 1;
				}
				if(sgn == -1 && sum >= 0){
					op += sum + 1;
					sum = -1;
				}
				sgn *= -1;
			}
			res = min(res, op);
		}
		cout << res << endl;
	}
}


Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 998244353;
const ll MAX = 1000001;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

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

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

struct edge {
	ll ind;
	ll fr;
	ll to;
	ll d;
};


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

ll diam(vector<vector<edge>> g, ll N) {

	queue<ll> q;
	vector<ll> dis(N + 1, -1);
	dis[1] = 0;
	q.push(1);

	while (!q.empty()) {
		ll v = q.front();
		q.pop();

		for (edge e : g[v]) {
			if (dis[e.to] != -1) { continue; }
			q.push(e.to);
			dis[e.to] = dis[v] + e.d;
		}
	}

	ll maxdis = -INF;
	ll maxid = 1;
	repn(i, N) {
		if (maxdis < dis[i]) {
			maxdis = dis[i];
			maxid = i;
		}
	}

	vector<ll> dis2(N + 1, -1);
	dis2[maxid] = 0;
	q.push(maxid);

	while (!q.empty()) {
		ll v = q.front();
		q.pop();

		for (edge e : g[v]) {
			if (dis2[e.to] != -1) { continue; }
			q.push(e.to);
			dis2[e.to] = dis2[v] + e.d;
		}
	}

	ll ret = -INF;
	repn(i, N) {
		ret = max(ret, dis2[i]);
	}

	return ret;

}


int main() {

	ll N;
	cin >> N;

	vector <vector<edge>> g(N + 1);

	repn(i, N - 1) {
		ll a, b;
		cin >> a>> b;
		g[a].push_back({ i,a,b,1 });
		g[b].push_back({ i,b,a,1 });
	}

	ll d = diam(g, N);

	if (d % 3 == 1) { cout << "Second"; }
	else { cout << "First"; }
	
	
	system("PAUSE");
}


Measured memory_bytes: 46184
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <vector>
using namespace std;

int main()
{
    const long long mod = 1000000007;
    long long n, k;
    cin >> n >> k;
    long long ans = 0;
    for (long long i = k; i <= n + 1; i++) {
        ans += i * (n + 1 - i) + 1;
        ans %= mod;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3192
#include<bits/stdc++.h>
#define ll long long
#define debug(x) cout<<#x<<'='<<x<<endl
#define set0(x) memset(x,0,sizeof(x))
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=2e5+10;
ll a[maxn],cnt[maxn];
ll f[maxn];
int main()
{
   int n;
   cin>>n;
   ll mx=0,sum=0;
   for(int i=1;i<=n;i++) cin>>a[i],cnt[a[i]]++,mx=max(mx,a[i]);
   for(int i=1;i<=mx;i++) sum+=(cnt[i]*(cnt[i]-1))/2,f[i]=(cnt[i]*(cnt[i]-1))/2;
    for(int i=1;i<=n;i++)
    {
        ll x=cnt[a[i]]-1;
        ll ans=x*(x-1)/2;
        ans=sum+ans-f[a[i]];
        cout<<ans<<endl;
    }
   //system("pause");
   return 0;
}


Measured memory_bytes: 6912
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pl;
typedef vector<ll> vl;

int main (void) {
  ios::sync_with_stdio(false);cin.tie(0);
  cout << fixed << setprecision(15);
  int k,a,b;
  cin >> k >> a >> b;
  for (int i = a; i <= b; i++) {
    if (i%k == 0) {
      cout << "OK\n";
      return 0;
    }
  }
  cout << "NG\n";
  return 0;
}



Measured memory_bytes: 3652
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
#include <vector>
#include <cstdio>
#include <bits/stdc++.h>
#include <set>
#include <stdio.h>
using namespace std;
using ll =long long;

int main (void) {
  string S;
  cin >> S;
  char P[1010]={' '};
  for (int i=0; i<S.size(); i++) P[S[i]]=1;
  puts((P['N']==P['S'] && P['W']==P['E'])?"Yes":"No");
  return 0;
}


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

int a,b,c;

int main(){
    cin >> a >> b >> c;

    if(a+b+c >= 22) dunk("bust");
    else dunk("win");
}
   

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(max(a)):
    cnt = 1 if a[0] - i >= 1 else 0
    for j in range(1, n):
        if a[j-1] - i < 1 and a[j] - i >= 1:
            cnt += 1
    ans += cnt
print(ans)

Measured memory_bytes: 9188
n = int(input())
a = list(map(int,input().split()))
a.sort(reverse=True)
# k_C_r
k =  a[0]
d_min = float('inf')
for i in range(1,n):
    d = abs(a[i] - k/2)
    if d < d_min:
        d_min = d
        r = a[i]

print(k,r)

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

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

	for (int i = 0; i < s.length(); ++i) {
		cout << char('A' + ((s[i] - 'A' + n) % 26));
	}
	
	return 0;
}
	

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<numeric>
#include<vector>
#include<set>
#include <math.h>
#include <string>
#define cinf(n,x,y) for(int i=0;i<(n);i++) cin >> x[i]>>y[i];
typedef long long int ll;
using namespace std;

int main(){
	string s; cin >>s;
	for(int i=0;i<12;i++){
		cout << s[i];
		if(i==3)cout << " ";
	}
	cout << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
#include <numeric>
#include<map>
 
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<n;i++)
#define all_map(itr,mp) for(auto itr=mp.begin();itr!=mp.end();itr++)
#define ALL(a) (a).begin(),(a).end()

ll number(ll a){
    if(a <=  0)return 0;
    return a%10 + number(a/10);
}
int main(){
    ll x;
    cin >> x;
    if(x%number(x) == 0)cout << "Yes";
    else cout << "No";
}

Measured memory_bytes: 256
#include<stdio.h>
short n, i;
short a;
int ans, odd;
int main(void){
  ans = odd = 1;
  scanf("%hd", &n);
  for(i=n-1; i>=0; i--){
    scanf("%hd", &a);
    ans *= 3;
    odd *= ((a&1)==0)+1;
  }
  printf("%d\n", ans-odd);
}

Measured memory_bytes: 128
n,m,x = map(int,input().split())

array = [list(map(int,input().split())) for _ in range(n)]

# print(array)
# print(n)
ans = 10 ** 8
for i in range(2**n):

    skill = [0] * m
    price = 0
    count = 0
    for k in range(n):
        if (i >> k) & 1:

            price += array[k][0]
            for j in range(m):
                skill[j] += array[k][j+1]
    for l in range(m):
        if skill[l] < x:
            break
        else:
            count += 1
    if count == m:
        ans = min(ans, price)

if ans == 10**8:
    print(-1)
else:
    print(ans)





Measured memory_bytes: 9220
#include <bits/stdc++.h>
 
using namespace std;
long long x,p[10001][100][2];
vector <long long> d;
string a;
long long cal(long long i,long long s,bool t)
{
    if (i==d.size())
        return !s;
    if (p[i][s][t]>-1)
        return p[i][s][t];
    long long tp=0,lim=(t)?d[i]:9;
    for (long long dg=0; dg<=lim; dg++)
    {
        bool nt=(dg<lim)?0:t;
        tp=(tp+cal(i+1,(s+dg)%x,nt))%1000000007;
    }
    return p[i][s][t]=tp;
}
long long ans(string num)
{
    memset(p,-1,sizeof(p));
    d.clear();
    for (int i=0;i<num.size();i++)
        d.push_back(num[i]-'0');
    return cal(0,0,1);
}
 
main()
{
    cin>>a>>x;
    cout<<(ans(a)+1000000006)%1000000007;
}

Measured memory_bytes: 16896
A, B, Q = gets.split(' ').map(&:to_i)
S = A.times.map { gets.to_i }
T = B.times.map { gets.to_i }
X = Q.times.map { gets.to_i }

X.each do |x|
  rsi = S.bsearch_index { |s| s >= x } # right shrine index
  rs = rsi ? S[rsi] : S.last
  ls = rsi ? S[rsi - 1] : rs

  rti = T.bsearch_index { |t| t >= x } # right temple index
  rt = rti ? T[rti] : T.last
  lt = rti ? T[rti - 1] : rt

  min_dist = Float::INFINITY
  [ls, rs].product([lt, rt]).each do |st| # 全8通りの順路の距離を探索
    min_dist = [
      min_dist,
      (x - st[0]).abs + (st[1] - st[0]).abs,
      (x - st[1]).abs + (st[0] - st[1]).abs,
    ].min
  end

  puts min_dist
end

Measured memory_bytes: 5684
#include"bits/stdc++.h"
using namespace std;

int f(int d[30],int m,int w)
{
    int a[30];
    for(int i=0;i<30;i++) a[i]=d[i];

    if(m==8) return 8;
    int x=0,y=0,g,co=1;
    for(int i=0;i<30;i++){
        if(i==0) g=a[i];
        else if(a[i]==g){
            co++;
        }
        else{
            if(co==9&&(y==0||y==4)) x++;
            else if(co==3) y++;
            co=1;
            g=a[i];
        }
    }
    if(co==9&&(y==0||y==4)) x++;
    else if(co==3) y++;

    if(x==2&&y==4){
        return m;
    }

    int b=8;
    if(w==0){
        swap(a[15],a[14]);
        swap(a[18],a[20]);
        for(int i=0;i<3;i++)
            swap(a[i],a[i+27]);
        for(int i=0;i<4;i++)
            b=min(b,f(a,m+1,i));
    }
    else if(w==1){
        swap(a[12],a[17]);
        swap(a[11],a[9]);
        for(int i=0;i<3;i++)
            swap(a[i+6],a[i+21]);
        for(int i=0;i<4;i++)
            b=min(b,f(a,m+1,i));
    }
    else if(w==2){
        swap(a[20],a[9]);
        swap(a[15],a[17]);
        for(int i=0;i<3;i++)
            swap(a[3*i],a[3*i+23]);
        for(int i=0;i<4;i++)
            b=min(b,f(a,m+1,i));
    }
    else if(w==3){
        swap(a[18],a[11]);
        swap(a[14],a[12]);
        for(int i=0;i<3;i++)
            swap(a[3*i+2],a[3*i+21]);
        for(int i=0;i<4;i++)
            b=min(b,f(a,m+1,i));
    }
    return b;
}

int main()
{
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        int a[30];
        int m=0;
        for(int j=0;j<30;j++)
            cin >> a[j];
        int ans=8;
        for(int j=0;j<4;j++){
                ans=min(ans,f(a,m,j));
        }
        cout << ans << endl;
    }
    return 0;
}



Measured memory_bytes: 3076
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define ll long long
#define N 200005
#define mod 1000000007
#define rep(i,j,k) for (ll i=j;i<=k;++i)
#define per(i,j,k) for (ll i=j;i>=k;--i)
using namespace std;
inline ll read(){
	char ch=getchar(); ll x=0,f=1;
	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	while (ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
	return x*f;
}
map<ll,ll>mp[N];
ll n,m;
int main(){
	n=read(); m=read();
	rep(i,1,m){
		ll u=read(),v=read();
		mp[u][v]=1; mp[v][u]=1;
	}
	rep(i,2,n-1) if (mp[1][i]&&mp[i][n]) return puts("POSSIBLE")&0;
	puts("IMPOSSIBLE");
}

Measured memory_bytes: 47104
#include <bits/stdc++.h>
using namespace std;
 
#define    int                      long long int
#define    ld                       long double
#define    f(i,j,n)                 for(int i = j; i <= n; i++)
#define    r(i,n,j)                 for(int i = n; i >= j; i--)
#define    mod                      1000000007
#define    speed                    ios_base::sync_with_stdio(false);
#define    upp                      cin.tie(NULL);
#define    pb                       push_back
#define    mp                       make_pair
#define    T                        int ttt; cin >> ttt; while(ttt--)
#define    ff                       first
#define    ss                       second
#define    all(container)            container.begin() , container.end()
#define    sz(container)            (int)container.size()
#define    pii                      pair <int , int>
#define    pll                      pair <long long int , long long int>

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

int32_t main()
{
    speed upp
    int n,x,y,z;
    cin>>n>>x>>y;
    int a[n+1][n+1];
    f(i,1,n)
    {
        f(j,1,n)
            a[i][j]=abs(j-i);
    }
    f(i,1,n)
    {
        f(j,i+1,n)
            a[i][j]=min(a[i][j],a[i][x]+a[y][j]+1);
    }
    int ff[n+1];
    f(i,0,n)
        ff[i]=0;
    f(i,1,n)
        f(j,i+1,n)
            ff[a[i][j]]++;
    f(i,1,n-1)
        cout<<ff[i]<<endl;
}

Measured memory_bytes: 31616