akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<cstdio>
#include<cstring>
#define rep(i,a,b) for(register int i=a;i<=b;i++)
using namespace std;
int n,m,root=0,tot=0;
int f[20][3],ans[1000010];
char s[1000010];
struct Tree{
	int ch[3],val,rev;
}t[3000010];
void setup(){
	f[0][1]=1;
	f[0][2]=2;
	for(register int i=1;i<=n;i++){
		f[i][1]=f[i-1][1]*3;
		f[i][2]=f[i-1][2]*3;
	}
}
void reverse(int x){
	t[x].rev^=1;
	swap(t[x].ch[1],t[x].ch[2]);
}
void pushdown(int x){
	if(t[x].rev){
		t[x].rev=0;
		reverse(t[x].ch[0]);
		reverse(t[x].ch[1]);
		reverse(t[x].ch[2]);
	}
}
void build(int &now,int k,int val){
	now=++tot;
	if(!k){
		t[now].val=val;
		return;
	}
	build(t[now].ch[0],k-1,val);
	build(t[now].ch[1],k-1,val+f[n-k][1]);
	build(t[now].ch[2],k-1,val+f[n-k][2]);
}
void rotate(int x,int k){
	swap(t[x].ch[0],t[x].ch[1]);
	swap(t[x].ch[0],t[x].ch[2]);
	if(!k)return;
	pushdown(x);
	rotate(t[x].ch[0],k-1);
}
void dfs(int x,int k,int val){
	if(!k){
		ans[t[x].val]=val;
		return;
	}
	pushdown(x);
	dfs(t[x].ch[0],k-1,val);
	dfs(t[x].ch[1],k-1,val+f[n-k][1]);
	dfs(t[x].ch[2],k-1,val+f[n-k][2]);
}
int main(){
	scanf("%d%s",&n,s+1);
	setup();
	m=strlen(s+1);
	build(root,n,0);
	rep(i,1,m){
		if(s[i]=='S'){
			reverse(root);
		}
		else{
			rotate(root,n);
		}
	}
	dfs(root,n,0);
	int lim=1;
	for(register int i=1;i<=n;i++)lim*=3;
	for(register int i=0;i<lim;i++)printf("%d ",ans[i]);
	return 0;
}

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

int main() {

  int a, b, c, d, e, k;
  cin >> a >> b >> c >> d >> e >> k;
  
  if(e-a <= k){
  	cout << "Yay!"<< endl;
  }
  else{
  	cout << ":("<< endl;
  }
  
}

Measured memory_bytes: 256
while True:
    H, W = map(int, input().split())
    if H == W == 0:
        break
    primary = ""
    secondary = ""
    for i in range(W):
        if i % 2 == 0:
            primary += "#"
            secondary += "."
        else:
            primary += "."
            secondary += "#"
    for i in range(H):
        if i % 2 == 0:
            print(primary)
        else:
            print(secondary)
    print()


Measured memory_bytes: 5608
#include <stdio.h>

#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }

template <typename T, typename V>
void __print(const pair<T, V> &x) {
    cerr << '{';
    __print(x.first);
    cerr << ',';
    __print(x.second);
    cerr << '}';
}
template <typename T>
void __print(const T &x) {
    int f = 0;
    cerr << '{';
    for (auto &i : x) cerr << (f++ ? "," : ""), __print(i);
    cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
    __print(t);
    if (sizeof...(v)) cerr << ", ";
    _print(v...);
}
#ifdef LOCAL
#define debug(x...)               \
    cerr << "[" << #x << "] = ["; \
    _print(x)
#else
#define debug(x...)
#endif

#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a;
    string s;
    cin >> a;
    cin >> s;
    if(a>=3200){
        cout << s << endl;
    }else{
        cout << "red" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
#define int long long
using P = pair<int,int>;
signed main(){
    int n;cin >> n;
    int a[n];
    rep(i,n)cin >> a[i];
    int x1 = 0;
    int s = 0;
    rep(i,n)s += a[i];
    for(int i = 1;i < n;i+=2)x1+= a[i];
    x1 = s - 2*x1;
    vector<int> ans;
    ans.push_back(x1);
    rep(i,n-1){

        int x = 2*a[i] - ans.back();
        ans.push_back(x);
    }
    for(auto p:ans)cout << p << endl;
    return 0;
}

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define FastRead ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long int
#define ld double
#define FOR(i,a,n) for (int i=(a);i<=(n);++i)
#define RFOR(i,a,n) for (int i=(n);i>=(a);--i)
#define FI(i,n) for (int i=0; i<(n); ++i)
#define ZERO(a) memset((a),0,sizeof((a)))
#define f first
// #define s second
#define pb push_back
#define mk make_pair
#define all(g) g.begin(),g.end()
int fastMax(int x, int y) { return (((y-x)>>(32-1))&(x^y))^y; }
int fastMin(int x, int y) { return (((y-x)>>(32-1))&(x^y))^x; }

// #include <ext/pb_ds/assoc_container.hpp> // Common file
// #include <ext/pb_ds/tree_policy.hpp>     // Including tree_order_statistics_node_updat
// using namespace __gnu_pbds;
// typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

// I am questioning life and universe and 
// everything else after looking at this

const ll MAXN = 105;
const ll MAXK = 1e5 + 5;
const ll MOD = 1e9 + 7;
ll n,p,dp[MAXN][MAXK],prefix[MAXN][MAXK],a[MAXN];

ll rec_dp(ll,ll);

ll rec_prefix(ll idx,ll candies){
    if(candies < 0) return 0;
    if(idx == 0) return 1;

    ll &ans = prefix[idx][candies];

    if(ans != -1) return ans;

    ans = (rec_prefix(idx,candies-1) + rec_dp(idx,candies))%MOD;

    return ans;
}

ll rec_dp(ll idx,ll candies){
    if(candies < 0) return 0;
    if(idx == 0) return 1;

    ll &ans = dp[idx][candies];

    if(ans != -1) return ans;

    ans = ((rec_prefix(idx-1,candies) - rec_prefix(idx-1,candies-a[idx]-1))%MOD + MOD)%MOD;

    return ans;
}

void solve(){
    cin>>n>>p;

    FOR(i,1,n) cin>>a[i];

    memset(dp,-1,sizeof(dp));
    memset(prefix,-1,sizeof(prefix));

    cout<<rec_dp(n,p)<<endl;
}

signed main(){


    ll t;
    t = 1; 
    // cin>>t;
    FOR(tt,1,t){
        solve();
    }
    
}

Measured memory_bytes: 168960
n, m, c = map(int, input().split())
b = list(map(int, input().split()))
a = []
for i in range(n):
  a.append(list(map(int, input().split())))

def inner_product(l1, l2):
  if len(l1) != len(l2):
    print('Error: length mismatch')
  else:
    ans = 0
    for i in range(len(l1)):
      ans += l1[i] * l2[i]
    return(ans)
ans = 0
for i in range(n):
  if inner_product(a[i], b) + c > 0:
    ans += 1
print(ans)

Measured memory_bytes: 38416
from collections import Counter

N = map(int, input().split())
As = list(map(int, input().split()))

lst = []
t = 0
for a in As:
  t += a
  lst.append(t)
  
dic = Counter(lst)

rlt = 0
for k in dic:
  if k == 0:
    rlt += dic[k]
  rlt += (dic[k]-1)*dic[k]//2
  
print(rlt)

Measured memory_bytes: 140948
import java.util.*

fun main(arr:Array<String>) {
    val (n,m) = readLine()!!.split(" ").map { it.toInt() }
    val numList = mutableListOf<Card>()
    numList.addAll(readLine()!!.split(" ").map { Card(it.toLong(), 1) })
    numList.addAll((1..m).map { readLine()!!.split(" ").map { it.toLong() }.let { Card(it[1], it[0].toInt()) } })

    var remain = n
    var ans = 0L
    for(c in numList.sortedByDescending { it.number }) {
        if(remain >= c.cont) {
            ans += (c.number * c.cont)
            remain -= c.cont
        } else {
            ans += (c.number * remain)
            remain = 0
            break
        }
    }
    println(ans)
}

class Card(val number:Long, val cont:Int):Comparable<Card> {
    override fun compareTo(other: Card): Int {
        return other.number.compareTo(this.number)
    }
}

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

int main(){
    int n,k;cin>>n>>k;
    vector<int> price(n);
    for (int i=0;i<n;i++){
        cin >> price[i];
    }

    sort(price.begin(), price.end());
    int acc = 0;
    for (int i=0;i<k;i++){
        acc += price[i];
    }
    cout << acc << endl;
    return 0;

}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define REP(i,j,n) for(int i = j;i < (n);i++)
#define intput(i) cout << i << endl
#define ll long long
#define stringput(s) cout << (string)(s) << endl

int main(){
  int A, B, X;
  cin >> A >> B >> X;
  if(A <= X && X <= A+B) cout << "YES" << endl;
  else cout << "NO" << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#define ll long long

typedef struct{
  ll A;
  ll B;
}energy;
int cmp(const void *p,const void *q){
  return ((energy*)p)->A-((energy*)q)->A;
}
void init(energy *t,int N);

int main(){
  int N,M;
  energy *E;
  ll ans=0;
  int i;

  scanf("%d%d",&N,&M);
  E=(energy*)malloc(sizeof(energy)*N);

  init(E,N);
  qsort(E,N,sizeof(energy),cmp);

  for(i=0;i<N;i++){
      if(E[i].B<=M){
        ans+=E[i].A*E[i].B;
        M-=E[i].B;
      }else{
        ans+=M*E[i].A;
        break;
      }
  }
  printf("%lld\n",ans);

  free(E);
  return 0;
}

void init(energy *t,int N){
  for(int i=0;i<N;i++)scanf("%lld%lld",&t[i].A,&t[i].B);
}

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

const ll nax=1e5+7;

ll M,n,down[nax],up[nax],dp2[nax];
vector<ll> edge[nax],luu[nax],pr[nax],sf[nax],child[nax];

void DFS1(int s,int par = -1){
	ll res=1;
	
	for (auto it :edge[s]){
		if (it!=par){
			DFS1(it,s);
			
			res=res*(down[it]+1)%M;
			
			child[s].push_back(it);
			luu[s].push_back(down[it]+1);
		}
	}
	
	down[s]=res;
}

void DFS2(int s,int par = -1){
	for (ll i=0;i<child[s].size();++i){
		auto it=child[s][i];

		up[it]=(up[s]+1)*((i>0)? pr[s][i-1] : 1)%M * ((i<child[s].size()-1)? sf[s][i+1] : 1)%M;
		
		dp2[it]=down[it]*(up[it]+1)%M;
		
		DFS2(it,s);
			
		
		
	}
}

int main(){
//	freopen("input.inp","r",stdin);
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>M;
	
	for (ll i=0;i<n-1;++i){
		ll a,b;
		cin>>a>>b;
		
		edge[a].push_back(b);
		edge[b].push_back(a);
	}
	
	DFS1(1);
	dp2[1]=down[1];
	
	for (ll i=1;i<=n;++i) {
//		for (auto it: luu[i]) cout<<it<<" ";
//		cout<<"\n";
		
		ll k=luu[i].size();
		pr[i].resize(k);sf[i].resize(k);
		
		for (ll j=0;j<k;++j) {
			if (j==0) pr[i][j]=luu[i][j];
			else pr[i][j]=(pr[i][j-1]*luu[i][j])%M;
		}
		
		for (ll j=k-1;j>=0;--j) {
			if (j==k-1) sf[i][j]=luu[i][j];
			else sf[i][j]=(sf[i][j+1]*luu[i][j])%M;
		}
	}
	
//	for (ll i=1;i<=n;++i) {
//		for (auto it: pr[i]) cout<<it<<" ";
//		cout<<"\n";
//		
//		for (auto it: sf[i]) cout<<it<<" ";
//		cout<<"\n";
//	}
//	cout<<"\n";
//	
//	for (ll i=1;i<=n;++i) cout<<down[i]<<" "<<up[i]<<"\n";
//	cout<<"\n";
	
	DFS2(1);
	
//	for (ll i=1;i<=n;++i) cout<<down[i]<<" "<<up[i]<<"\n";
//	cout<<"\n";
	
	for (ll i=1;i<=n;++i) cout<<dp2[i]<<"\n";
}

Measured memory_bytes: 43088
#include <iostream>

using namespace std;
#define ll long long
int main(){
    int ans=0;
    int n=0;
    cin>>n;
    int a,b,c;
    b=-1;
    c=-2;
    for(int i=0;i<n;i++){
        cin>>a;
//            cout <<a<<"aaz" <<b<<"dss"<< c<<endl;
        if (a==b){
//            cout <<a<<"aaz" <<b<< endl;
            if(a==c&&c>0){
                b=10001;
            }else{
                ans++;
            }
        }
        if (b==-1){
            c=b;
            b=a;
        }else{
            c=b;
            b=a;
        }
    }
    cout <<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
s = input()
n = len(s)
s = int(s,2)

if n % 2 == 0:
    a = int("10"*(int(n/2)),2)
    b = int("01"*(int(n/2)),2)
else:
    a = int("10"*(int((n-1)/2)) + "1", 2)
    b = int("01"*(int((n-1)/2)) + "0", 2)

ansa = bin(s^a).count("1")
ansb = bin(s^b).count("1")
print(min(ansa,ansb))

Measured memory_bytes: 3244
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+7;
int n,k,ans,a[N];
bool check(int x)
{
	long long num=0;
	for(int i=1;i<=n;i++)if(a[i]%x==0)num+=a[i]/x-1;else num+=a[i]/x;
	return(num<=k);
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),ans=max(ans,a[i]);
	int l=1,r=ans-1,mid;
	while(l<=r)
	{
		mid=l+r>>1;
		if(check(mid))ans=mid,r=mid-1;
		else l=mid+1;
	}
	printf("%d",ans);
}

Measured memory_bytes: 4536
#include <iostream>

int main()
{
    bool ok = false;
    int K, A, B;
    std::cin >> K >> A >> B;

    int num = K;

    while (num <= B)
    {
        if (num >= A && num <= B)
        {
            ok = true;
            std::cout << "OK";
            break;
        }

        num += K;
    }

    if (!ok)
    {
        std::cout << "NG";
    }
}

Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<int,int> P;
const LL mod=1000000007;
const LL LINF=1LL<<62;
const LL INF=1<<17;

int N;
LL K;
LL dp[41][2];
vector<LL> a;

LL rec(int k,bool c){
    if(k<0) return 0;
    if(~dp[k][c]) return dp[k][c];
    LL ret=0;
    LL mx=c?(K&(1LL<<k))>>k:1;
    for (int s = 0; s <= mx; s++) {
        LL tmp=0;
        for (int i = 0; i < N; i++) {
            tmp+=(a[i]&1LL<<k)^(static_cast<LL>(s)<<k);
        }
        tmp=tmp+rec(k-1,c&(s==mx));
        ret=max(ret,tmp);
    }
    return dp[k][c]=ret;
}




int main(){
    cin >> N >> K;
    LL p=K;
    int k=0;
    while(p){
        k++;
        p/=2;
    }
    memset(dp,-1,sizeof(dp));
    LL sum=0;
    for (int i = 0; i < N; i++) {
        LL A;
        cin >> A;
        for (int j = k; j < 40; j++) {
            sum+=A&(1LL<<j);
        }
        a.pb(A);
    }
    cout << sum+rec(k-1,true) << endl;
    return 0;
}



Measured memory_bytes: 1400
import java.util.Scanner;

class Main {

	int m, f, r;

	public void gr() {

		Scanner sc = new Scanner(System.in);

		m = sc.nextInt();

		f = sc.nextInt();

		r = sc.nextInt();

		while(m != -1 || f != -1 || r != -1) {

			if(m == -1 || f == -1) {

				System.out.println("F");

			} else if(m + f >= 80) {

				System.out.println("A");

			} else if(m + f >= 65) {

				System.out.println("B");

			} else if(m + f >= 50) {

				System.out.println("C");

			} else if(m + f >= 30) {

				if(r >= 50) {

					System.out.println("C");

				} else {

				System.out.println("D");

				}

			} else {

				System.out.println("F");

			}

			m = sc.nextInt();

			f = sc.nextInt();

			r = sc.nextInt();

		}

	}

	public static void main(String[] args) {

		new Main().gr();

	}

}

Measured memory_bytes: 26344
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <iomanip>

int main(void) {
	// in
	std::string s;
	std::cin >> s;

	bool is_bad = false;
	for(int i = 0; i < 3; ++i) {
		if(s[i] - '0' == s[i+1] - '0') is_bad = true;
	}

	std::cout << (is_bad ? "Bad" : "Good") << std::endl;

	return 0;
}


Measured memory_bytes: 256
N, M = map(int,input().split())

H = list(map(int, input().split()))
H.insert(0, 0)

V = [list(map(int, input().split())) for i in range(M)]

count = 0

dic = {}

for i in range(1, N+1):
  dic[i] = set()

for hen in V:
  dic[hen[0]].add(hen[1])
  dic[hen[1]].add(hen[0])

print(sum(all([H[i] > H[hs] for hs in dic[i]]) for i in range(1, N+1)))

Measured memory_bytes: 65892
#include <bits/stdc++.h>
		using namespace std;
		
		typedef long long ll;
		#define pi 3.14159265 
		#define EPS 1e-8
		
		#define mod 1000000007
		#define fi first
		#define se second
		#define mp make_pair
		#define pb push_back
		#define endl "\n"

		const ll INF=(ll)2e18;
		
		long long binpow(long long a, long long b, long long m) {
		a %= m;
		long long res = 1;
		while (b > 0) {
			if (b & 1)
				res = res * a % m;
			a = a * a % m;
			b >>= 1;
		}
		return res;
	}
			 ll fac[100050]={0};
		
		
		
		ll modinverse(ll a, ll m)
		{
			return binpow(a,m-2,m);
		}
		ll ncr(ll n,ll r)
		{
			return (((fac[n]*modinverse(fac[r],mod))%mod )*modinverse(fac[n-r],mod))%mod;
		}
		
		int main()
		{
			 ios_base::sync_with_stdio(false);
			 cin.tie(NULL);
			
			 ll n;
			 cin>>n;
			 
		
			 fac[0]=fac[1]=1;
			 for(ll i=2;i<=1e5+5;i++)
			 {
				 fac[i]=fac[i-1]*i;
				 fac[i]%=mod;
			 }
			 
			 vector<ll> v(n+2);
			 map<ll,ll> pos;
			 ll p1=0,p2=0;
			 for(ll i=1;i<=(n+1);i++)
			 {
				 cin>>v[i];
				 if(pos[v[i]]!=0)
				 {
					 p1=pos[v[i]]-1;
					 p2=n+1-i;
				//	 cout<<p1<<" "<<p2<<endl;
				 }
				 pos[v[i]]=i;
				 
			 }
			 
			 cout<<n<<endl;
			 for(ll i=2;i<=n;i++)
			 {
				 ll r1=ncr(n+1,i);
				 if((p1+p2)>=(i-1))
				 {	
					  r1-=ncr(p1+p2,i-1);}
				 r1+=mod;
				 r1%=mod;
			//	 if(p2>=(i-1))
			//	 r1-=ncr(p2,i-1);
			//	 r1+=mod;
			//	 r1%=mod;
				cout<<r1<<endl;
			 }
			 cout<<1<<endl;
			 
			
		}
						
					 
				 


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

long long int modPow(long long int a,long long int b,long long int mod)
{
    if(b==0)
        return 1;
    long long int p = modPow(a,b/2,mod)%mod;
    p=(p*p)%mod;
    return (b%2==0)? p : (a*p)%mod;
}

int main()
{
    int N {};
    const long long int mod {static_cast<long long int>(1e9+7)};
    cin >> N;
    if(N==1)
        cout << 0;
    else
    {
        long long int ans=(modPow(10,N,mod)-modPow(9,N,mod)-modPow(9,N,mod)+modPow(8,N,mod))%mod;
        cout << (ans+mod)%mod;
    }
    return 0;
}

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

typedef pair<ll, ll> P;

void fail(){
	cout << -1 << endl;
	exit(0);
}

P f(ll a, ll l, ll r){
	if(r <= a) fail();

	P ret;
	ll ng = 0, ok = 2e9;
	while(abs(ng - ok) > 1){
		ll mid = (ng + ok) / 2;
		if(a * mid >= l) ok = mid;
		else ng = mid;
	}
	ret.first = a * ok;
	ok = 0, ng = 2e9;
	while(abs(ng - ok) > 1){
		ll mid = (ng + ok) / 2;
		if(a * mid < r) ok = mid;
		else ng = mid;
	}
	ret.second = a * ok;
	return ret;
}


ll a[100000];
int K;

ll sim(ll n){
	for(int i = 0; i < K; i++){
		n -= n % a[i];
		if(n == 0) return 0;
	}
	return n;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
#ifdef LOCAL
	std::ifstream in("in");
	std::cin.rdbuf(in.rdbuf());
#endif

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

	if(a[K - 1] != 2){
		fail();
	}

	ll ng1 = 0, ok1 = 1e18;
	while(abs(ok1 - ng1) > 1){
		ll mid = (ng1 + ok1) / 2;
		if(sim(mid) >= 2) ok1 = mid;
		else ng1 = mid;
	}
	ll ok2 = 1, ng2 = 1e18;
	while(abs(ok2 - ng2) > 1){
		ll mid = (ng2 + ok2) / 2;
		if(sim(mid) <= 2) ok2 = mid;
		else ng2 = mid;
	}
	if(ok1 <= ok2){
		cout << ok1 << " " << ok2 << endl;
	}
	else{
		cout << -1 << endl;
	}
	return 0;

	P p = { 2, 2 };
	for(int i = K - 2; i >= 0; i--){
		P x = f(a[i], p.first, p.second + a[i + 1]);
		cout << x.first << " " << x.second << endl;
		if(x.second < x.first) fail();
		p = x;
	}

	cout << p.first << " " << p.second + a[0] - 1 << endl;
}


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

using namespace std;

int main(int argc, char *argv[]) {
    int r, D, x2000;
    cin >> r >> D >> x2000;

    int64_t ans = x2000;
    for (int i = 2001; i <= 2010; i++) {
        ans = ans * r - D;
        cout << ans << endl;
    }

    return 0;
}


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


def main():
    from collections import Counter

    n = int(input())
    results = Counter([input() for _ in range(n)])

    for status in ['AC', 'WA', 'TLE', 'RE']:
        print(status + ' x ' + str(results[status]))


if __name__ == '__main__':
    main()


Measured memory_bytes: 16580
#include <bits/stdc++.h>
using namespace std;
int main(){
string S; 
cin >> S; 
int A[30] = {}; 
for(int i = 0; i < S.size(); i++){
A[S.at(i) - 'a'] ++; 
}
int mini = 1111111; 
for(int i = 0; i < 26; i++){
mini = min(mini, A[i]); 
}
if(mini > 0){
cout << "None" << endl; 
}
else{
for(char c = 'a'; c <= 'z'; c++){
if(A[c - 'a'] == 0){
cout << c << endl; 
  break;
}
}
}
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct qu
{
    int a,b,c,d;
}x[25];
bool cmp(qu u,qu v)
{
    return u.d>v.d;
}
int A[15];
int n,m,q;
int ans;
void dfs(int cur,int now)  // 最大能取的数,当前为第 now 个数
{
    if(cur==0||now>n) return;
    if(now==n)   // 计算一次符合的数
    {
        //for(int i=1;i<=n;i++) cout<<A[i]<<" ";
        //cout<<endl;
        int sum=0;
        for(int i=0;i<q;i++)
        {
            if(A[x[i].a]-A[x[i].b]==x[i].c)
                sum+=x[i].d;
        }
        ans=max(ans,sum);
        return;
    }
    for(int i=cur;i>=1;i--)
    {
        A[now+1]=i;
        dfs(i,now+1);
    }
}
int main()
{
    cin>>n>>m>>q;
    for(int i=0;i<q;i++)
    {
        scanf("%d%d%d%d",&x[i].a,&x[i].b,&x[i].c,&x[i].d);
    }
    sort(x,x+q,cmp);
    for(int i=m;i>=1;i--)
    {
        A[1]=i;
        dfs(i,1);
    }
    cout<<ans;
}


Measured memory_bytes: 3760
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vs vector<string>
#define mii map<int, int>

void show(auto a){
  int i = 0;
  while(i < a.size()){
    cout<<a[i]<<" ";
    i++;
  }
  cout<<endl;
}


int main(){
  ios_base::sync_with_stdio(false);
  int n;
  cin>>n;
  vi a(n+1), b(n+1), c(n+1);
  for(int i = 1; i <= n; i++) cin>>a[i]>>b[i]>>c[i];


  int dp[n+1][3];
  dp[1][0] = a[1];
  dp[1][1] = b[1];
  dp[1][2] = c[1];

  for(int i = 2; i <= n; i++){
  	for(int j = 0; j < 3; j++){
  		if(j == 0){
  			dp[i][j] = a[i] + max(dp[i-1][1], dp[i-1][2]);
  		}else if(j == 1){
  			dp[i][j] = b[i] + max(dp[i-1][0], dp[i-1][2]);
  		}else if(j == 2){
  			dp[i][j] = c[i] + max(dp[i-1][1], dp[i-1][0]);
  		}
  	}
  }

  // for(int i = 1; i<= n; i++){
  // 	for(int j = 0; j < 3; j++){
  // 		cout<<dp[i][j]<<" ";
  // 	}
  // 	cout<<endl;
  // }

  int finalAns = max(dp[n][0], dp[n][1]);
  finalAns = max(finalAns, dp[n][2]);

  cout<<finalAns<<endl;
}

Measured memory_bytes: 2560
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<limits>
#include<algorithm>
#include<numeric>

int main(){
    int r, D, x;
    std::cin >> r >> D >> x;

    for(int i=0;i<10;i++){
        x = r*x-D;
        std::cout << x << std::endl;
    }

    return 0;
}

Measured memory_bytes: 256
import sys
from io import StringIO
import unittest


def resolve():
    # s = input()
    n = int(input())
    # a, b = map(int, input().split())
    # l = [list(map(int, input().split())) for _ in range(n)]

    if n >= 30:
        print('Yes')
    else:
        print('No')


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """25"""
        output = """No"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """30"""
        output = """Yes"""
        self.assertIO(input, output)


if __name__ == "__main__":
    # unittest.main()
    resolve()


Measured memory_bytes: 16216
#include<bits/stdc++.h>
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define inf 1010000000
#define infll 1010000000000000000ll
#define vi vector<int>
#define vll vector<ll>
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define mpr make_pair
#define fi first
#define se second
#define pq priority_queue<int>
#define pqll priority_queue<ll>
#define up(x,y) (x<(y)?x=(y):0)
#define dn(x,y) (x>(y)?x=(y):0)
#define ad(x,y) (x=(x+(y))%mod)
#define cbn(x,y) ((ll)fac[x]*inv[y]%mod*inv[(x)-(y)]%mod)
using namespace std;

int read(); ll readll();

int n; char ch[1000009];
bool check(int B){
	int i,x=0,y=B,z=2;
	for (i=1; i<=n; i++) if (ch[i]=='0'){
		x--; y--; if (z<2) z^=1;
		if (x<0) x=0; if (z<2 && (x&1)!=z) x=1;
		if (x>y) return 0;	
	} else if (ch[i]=='1'){
		x++; y++; if (z<2) z^=1;
		if (y>B) y=B; if (z<2 && (y&1)!=z) y--;
		if (x>y) return 0;
	} else{
		if (z==2){
			if (x==y) z=y&1^1; x--; y++;
			if (x<0) x=0; if (z<2 && (x&1)!=z) x++;
			if (y>B) y=B; if (z<2 && (y&1)!=z) y--;
			if (x>y) return 0;
		} else{
			x--; y++; z^=1;	
			if (x<0) x=0; if ((x&1)!=z) x++;
			if (y>B) y=B; if ((y&1)!=z) y--;
			if (x>y) return 0;
		}
	}
	return 1;
}
int main(){
	scanf("%s",ch+1); n=strlen(ch+1);
	int l=1,r=n,mid;
	while (l<r){
		mid=l+r>>1;
		if (check(mid)) r=mid; else l=mid+1;	
	}
	printf("%d\n",l);
	return 0;
}

int read(){
	int x=0; char ch=getchar(); bool flag=0;
	while (ch<'0' || ch>'9'){ if (ch=='-') flag=1; ch=getchar(); }
	while (ch>='0' && ch<='9'){ x=x*10+ch-'0'; ch=getchar(); }
	return flag?-x:x;
}
ll readll(){
	ll x=0; char ch=getchar(); bool flag=0;
	while (ch<'0' || ch>'9'){ if (ch=='-') flag=1; ch=getchar(); }
	while (ch>='0' && ch<='9'){ x=x*10+ch-'0'; ch=getchar(); }
	return flag?-x:x;
}


Measured memory_bytes: 4764
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll MOD = 998244353;
const ll INF = (ll)1000000007 * 1000000007;
const double EPS = 1e-9;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-11;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
int main() {
	string s, t; cin >> s >> t;
	int len = s.length(); len--;
	bool f = false;
	rep(i, 105) {
		if (s == t)f = true;
		string u = s.substr(0, len);
		s = s[len] + u;
	}
	if (f)cout << "Yes" << endl;
	else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	int train[100],n,i=0;
	while(scanf("%d",&n)!=EOF){
		if(n==0){
			printf("%d\n",train[i-1]);
			i--;
			}
		else{
			train[i]=n;
			i++;
			}
	}
	return 0;
}

Measured memory_bytes: 596
#include <bits/stdc++.h>
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end() 
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define INF 1000000000
using namespace std;
typedef long long ll;

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

    int ans;
    if(A >= 13) ans = B;
    else if (A < 13 and A >= 6) ans = B/2;
    else ans = 0;

    cout << ans << endl;
}

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

#if defined(DEBUG)

#include <unistd.h>
#include <sys/fcntl.h>
#define DLOG(...)        cerr << dbgFormat(__VA_ARGS__) << endl
#define DCALL(func, ...) func(__VA_ARGS__)

template <class... Args>
string dbgFormat(const char* fmt, Args... args) {
  size_t len = snprintf(nullptr, 0, fmt, args...);
  char buf[len + 1];
  snprintf(buf, len + 1, fmt, args...);
  return string(buf);
}

#else  // defined(DEBUG)

#define DLOG(...)
#define DCALL(func, ...)

#endif // defined(DEBUG)
// ----------------------------------------------------------------------

// ----------------------------------------------------------------------
typedef pair<int, int> Pair;

int myInf = 1e9;

int main(int argc, char *argv[]) {
#if defined(DEBUG)
  // GDB on Cygwin ignores redirection at run command.
  if (argc == 2) dup2(open(argv[1], 0), 0);
#else
  // For performance.  We should not use C-style stdio functions
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  cout << setprecision(20);

  int N, M; cin >> N >> M;

  int full = (1 << N) - 1;
  vector<int> v(full + 1, myInf);
  v.at(0) = 0;

  for (int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    int x = 0;
    for (int j = 0; j < b; j++) {
      int c;
      cin >> c; c--;
      x |= (1 << c);
    }

    for (int y = 0; y <= full; y++) {
      int cup = y | x;
      v.at(cup) = min(v.at(cup), v.at(y) + a);
    }

  }


  if (v.at(full) == myInf) {
    cout << -1 << endl;
  }else {
    cout << v.at(full) << endl;
  }

  return 0;
}



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

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

const ll MOD = 1e9+7;
// const ll MOD = 998244353;
const ll INF = 1ll<<60;

#define FOR(i,a,b) for (ll i=(a);i<(ll)(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define DEBUG(x) ;
#define DEBUG(x) std::cerr << #x << " : " << (x) << std::endl;

int dx[4]{0, 1, 0, -1};
int dy[4]{1, 0, -1, 0};



int main(int argc, char **argv)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll N, K; cin >> N >> K;
	vector<ll> A(N); REP(i, N) cin >> A[i], --A[i];

	ll logk{0};
	while ((1ll<<logk) < K) ++logk;
	vector<vector<ll>> ding(logk, vector<ll>(N));
	REP(i, N)
		ding[0][i] = A[i];

	REP(k, logk-1)
		REP(i, N)
			ding[k+1][i] = ding[k][ding[k][i]];

	ll now{0};
	for (ll bit = 0;; ++bit)
	{
		if (K & 1) now = ding[bit][now];
		K=K>>1;
		if(K==0)break;
	}

	std::cout << now + 1 << std::endl;
	return 0;
}


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

vector<int> a(int t){
  vector<int> ret;
  ret.push_back(t/3600); t%=3600;
  ret.push_back(t/60); t%=60;
  ret.push_back(t);
  return ret;
}

int main(){
  int h, m, s;
  while(cin>>h>>m>>s){
    if(h==-1)break;
    vector<int> ans=a(7200-(3600*h+60*m+s));
    printf("%02d:%02d:%02d\n", ans[0], ans[1], ans[2]);
    ans=a(3*(3600*ans[0]+60*ans[1]+ans[2]));
    printf("%02d:%02d:%02d\n", ans[0], ans[1], ans[2]);
  }
  return 0;
}

Measured memory_bytes: 1212
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <fstream>
using LL=long long;
using std::cout;using std::endl;using std::cin;
using std::vector;using std::string;using std::set;using std::multiset;
using std::pair;using std::map;
using std::min;using std::max;
using std::make_pair;using std::swap;
std::ostream& operator<<(std::ostream& os,std::map<int,int>& obj){for(std::map<int,int>::iterator itr=obj.begin();itr!=obj.end();itr++){os<<itr->first<<"^"<<itr->second<<" ";}return os;}
std::ostream& operator<<(std::ostream& os,std::vector<std::map<int,int>>& obj){for(auto itr=obj.begin();itr!=obj.end();itr++){os<<*itr<<std::endl;}return os;}
std::ostream& operator<<(std::ostream& os,std::vector<int>& obj){for(auto itr=obj.begin();itr!=obj.end();itr++){os<<*itr<<" ";}return os;}
std::ostream& operator<<(std::ostream& os,std::vector<std::vector<int>>& obj){for(auto itr=obj.begin();itr!=obj.end();itr++){os<<*itr<<std::endl;}return os;}

namespace ndifix{
template<class T> void sort(T &v){std::sort(v.begin(),v.end());}
template<class T> void rsort(T &v){std::sort(v.rbegin(),v.rend());}
}

int main(){
  int n;cin>>n;
  vector<int> a(n);for(int i=0;i<n;i++)cin>>a[i];
  ndifix::sort(a);
  vector<pair<int,int>> ans;
  int M,m;m=a[0];M=a.back();a.pop_back();a.erase(a.begin());
  while(a.size() && a.back()>=0){
    ans.push_back(make_pair(m,a.back()));
    m-=a.back();a.pop_back();
  }
  while(a.size()){
    ans.push_back(make_pair(M,a.back()));
    M-=a.back();a.pop_back();
  }
  ans.push_back(make_pair(M,m));
  cout<<M-m<<endl;
  for(int i=0;i<ans.size();i++)cout<<ans[i].first<<" "<<ans[i].second<<endl;
}


Measured memory_bytes: 3188
#include <iostream>
#include <vector>
#include <string>
#include <map>

using namespace std;


int main() {
    string str;
    getline(cin, str);

    char c;

    for (int i=0; i<str.length();i++){
        if ( 64 < str[i] && str[i] <  91){
            c = str[i] + 32;
            cout << c;
        }
        else if( 96 < str[i] && str[i] <  123){
            c = str[i] - 32;
            cout << c;
        }
        else {
            cout << str[i];
        }
    }
    cout << endl;
}


Measured memory_bytes: 3204
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i, a, b) for(int i = a, i##_len = (b); i < i##_len; ++i)

int main()
{
    int H, W, N;
    cin >> H >> W >> N;
    cout << min((N%H) ? N/H + 1 : N/H,
                (N%W) ? N/W + 1 : N/W) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string S;cin>>S;
  string H=S;
  reverse(S.begin(),S.end());
  for(int X=0;X<S.size();X++){
    if(S[X]=='p'){
      S[X]='q';
    }
    else if(S[X]=='q'){
      S[X]='p';
    }
    if(S[X]=='b'){
      S[X]='d';
    }
    else if(S[X]=='d'){
      S[X]='b';
    }
  }
  if(H==S){
    cout<<"Yes"<<endl;
  }
  else{
    cout<<"No"<<endl;
  }
}


Measured memory_bytes: 3820
n = int(input())
s = []
not_ten = []
sum = 0
for i in range(n):
    buf = int(input())
    if buf%10 != 0:
        not_ten.append(buf)
    sum += buf

if sum%10 == 0:
    if not not_ten:
        print(0)
    else:
        print(sum - sorted(not_ten)[0])
else:
    print(sum)


Measured memory_bytes: 2940
{-# OPTIONS_GHC -O2 #-}
{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE BangPatterns #-}
module Main where

import           Data.List
import           Control.Monad
import           Debug.Trace
import qualified Data.ByteString.Char8         as BC
import           Data.Maybe                     ( fromJust, fromMaybe )
import qualified Data.Set                      as S
import qualified Data.IntMap.Strict            as IM
import qualified Data.IntMap.Lazy            as IML
import qualified Data.Map.Strict               as M
import           Data.Char
import qualified Data.Array.IArray as A
import qualified Data.Array.Unboxed as UA
import Data.Bits
import Control.Monad.State.Strict
import qualified Data.Array.ST as STA
import qualified Data.Array.IO as IOA
import qualified Data.Array.MArray as MA
import Control.Monad.ST
import System.IO (stdin)
import Control.Arrow
import qualified Data.Vector.Unboxed as UV
import qualified Data.Vector.Generic as GV



readTuple2 :: IO (Int, Int)
readTuple2 = do
    [a, b] <- readInts
    return (a, b)

readTuple3 :: IO (Int, Int, Int)
readTuple3 = do
    [a, b, c] <- readInts
    return (a, b, c)

readInt :: IO Int
readInt = fst . fromJust . BC.readInt <$> BC.getLine

readInts :: IO [Int]
readInts = map (fst . fromJust . BC.readInt) . BC.words <$> BC.getLine

split :: (a -> Bool) -> [a] -> [[a]]
split f [] = []
split f as =
    let (fo, la) = span f as
        las      = case la of
            [] -> []
            xs -> split f $ tail xs
    in  case fo of
            [] -> las
            xs -> xs : las

solve :: Int -> [(Int, Int)] -> Double
solve n as = (/len) . sum $ calcRoute <$> allRoute where
    len = fromIntegral $ length allRoute
    vec :: UV.Vector (Int, Int)
    vec = GV.fromList as
    routes :: StateT (S.Set Int) [] [Int]
    routes = do
        a <- get
        let bs = filter (`S.notMember` a) [0..n-1]
        case bs of
            [] -> pure []
            bs -> do
                b <- lift bs
                modify' $ S.insert b
                r <- routes
                pure $  b : r
    allRoute :: [[Int]]
    allRoute = evalStateT routes S.empty
    calcDist (x, y) (xx, yy) = sqrt . fromIntegral $ (xx - x) ^2  + (yy - y) ^2
    calcRoute :: [Int] -> Double
    calcRoute rx = foldl' (\t (p, n) -> calcDist (vec GV.! p) (vec GV.! n) + t ) 0 $ zip rx $ tail rx




main = do
    n <- readInt
    as <- replicateM n readTuple2
    print $ solve n as


Measured memory_bytes: 18812
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>
#include <string>

using namespace std;
using ll = long long;
using ull = size_t;

ll K;

void input() {
    cin >> K;
}

void solve() {
    deque<ull> bfs;
    bfs.push_back(1);
    vector<ull> dist(K, 100);
    dist[1] = 1;
    while (not bfs.empty()) {
        auto n = bfs.front(); bfs.pop_front();
        if (n == 0) {
            cout << dist[n] << endl;
            return;
        }
        auto ln = (n * 10) % K;
        if (dist[ln] > dist[n]) {
            dist[ln] = dist[n];
            bfs.push_front(ln);
        }
        auto un = (n + 1) % K;
        if (dist[un] > dist[n] + 1) {
            dist[un] = dist[n] + 1;
            bfs.push_back(un);
        }
    }
    
}

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



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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)

using namespace std;
const int INF = 1 << 30;
const long long MOD = 1000000000 + 7;
const double PI = acos(-1);

int main() {
	string S; cin >> S;
	int num1 = atoi(S.substr(0, 2).c_str());
	int num2= atoi(S.substr(2).c_str());
	if (1<=num1 && num1<=12) {
		if (1 <= num2 && num2 <= 12)cout << "AMBIGUOUS";
		else cout << "MMYY";
	}
	else {
		if (1 <= num2 && num2 <= 12)cout << "YYMM";
		else cout << "NA";
	}
}

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

int main(){

  int K=0;
  cin>>K;
  
  ll sum=0;
  for(int i=1;i<K+1;i++){
	for(int j=1;j<K+1;j++){
		for(int l=1;l<K+1;l++){
		
          
          int ans=gcd(__gcd(i,j),l);
          sum+=ans;
        }
    }
  }
  
  cout<<sum<<endl;
}



Measured memory_bytes: 3624
// Problem : D - Sum of Large Numbers
// Contest : AtCoder - AtCoder Beginner Contest 163
// URL : https://atcoder.jp/contests/abc163/tasks/abc163_d
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db long double
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define mi map<int,int>
#define ml map<ll,ll>
#define mii map<pii,int>
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define sz(x) (int)x.size()
#define mod 1000000007
#define MAX 4294967295
#define EPS 1e-9
#define io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define MAXN 15000005
#define inf 1e10
#define PI acos(-1.0)
#define int long long

int s(int x){ return x*(x+1)/2; }

void solve(){
    int n,k;
    cin>>n>>k;
    int ans = 0;
    int mx, mn = 0;
    for(int i=k;i<=n+1;i++){
        mn = s(i) % mod;
        mx = (s(n+1)-s(n-i+1)+mod) % mod;
        ans = (ans+mx-mn+1+mod)%mod;
    }
    cout<<ans<<endl;
}

signed main(){
    io;
    //freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
    int t;
    //cin>>t;
    t = 1;
    while(t--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 3640
#include<iostream>
#include<algorithm>
using namespace std;
const int N=501;
int a[501*501],X[501];
int c[N],cnt[N];
int pos[N][N],num[N];
int n;
bool cmp(int a,int b)
{
	return X[a]<X[b];
}
bool check()
{
    for(int i=1;i<=n*n;i++)
        pos[a[i]][++num[a[i]]]=i;
    for(int i=1;i<=n;i++)
        if(pos[i][i]!=X[i]) return false;
    return true;
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) 
		cin>>X[i],c[i]=i,a[X[i]]=i,cnt[i]=i-1;
    sort(c+1,c+1+n,cmp);
    for(int i=1;i<=n*n;i++)
        if(!a[i])
	        for(int j=1;j<=n;j++)
	            if(cnt[c[j]])
	            {
					a[i]=c[j];cnt[c[j]]--;break;
				}
    for(int i=1;i<=n;i++)
		cnt[i]=n-i;
    for(int i=n*n;i>=1;i--)
        if(!a[i])
        	for(int j=n;j>=1;j--)
            	if(cnt[c[j]])
				{
					a[i]=c[j];cnt[c[j]]--;break;
				}
    if(check())
    {
        cout<<"Yes\n";
        for(int i=1;i<=n*n;i++)
            cout<<a[i]<<" ";
    }
    else cout<<"No";
    return 0;
}

Measured memory_bytes: 3072
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define eb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pi M_PI
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T,vector<T>,greater<T>>
#define dame(a) {out(a);return 0;}
#define decimal cout<<fixed<<setprecision(15);
#define dupli(a) a.erase(unique(all(a)),a.end())
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef tuple<ll,ll,ll,ll> PPP;
typedef multiset<ll> S;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
using vvvvi=vector<vvvi>;
using vp=vector<P>;
using vvp=vector<vp>;
using vb=vector<bool>;
using vvb=vector<vb>;
const ll inf=1001001001001001001;
const ll INF=1001001001;
const ll mod=1000000007;
const double eps=1e-10;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void yesno(T b){if(b)out("yes");else out("no");}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}
template<class T> void noyes(T b){if(b)out("no");else out("yes");}
template<class T> void NoYes(T b){if(b)out("No");else out("Yes");}
template<class T> void NOYES(T b){if(b)out("NO");else out("YES");}
void outs(ll a,ll b){if(a>=inf-100)out(b);else out(a);}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll modpow(ll a,ll b){a%=mod;if(b==0)return 1;if(b&1)return a*modpow(a,b-1)%mod;ll k=modpow(a,b/2);return k*k%mod;}
vi parent,rankk,sz;
void init(ll n){
    parent=vi(n);
    rankk=vi(n);
    sz=vi(n,1);
    rep(i,n)parent[i]=i;
}
ll root(ll i){if(parent[i]==i)return i;return root(parent[i]);}
ll getsize(ll i){return sz[root(i)];}
bool same(ll a,ll b){return root(a)==root(b);}
bool heigou(ll x,ll y){
    x=root(x);y=root(y);
    if(x==y)return false;
    if(rankk[x]<rankk[y]){parent[x]=y;sz[y]+=sz[x];}
    else{parent[y]=x;sz[x]+=sz[y];}
    if(rankk[x]==rankk[y])rankk[x]++;
    return true;
}
int main(){
    ll n,m,q;cin>>n>>m>>q;
    vvi v(q,vi(3));
    rep(i,q)rep(j,3)cin>>v[i][j];
    if(m==n-1){
        rep(i,q)if(v[i][2])dame("No");
        dame("Yes");
    }
    init(n);
    ll cnt=n;
    rep(i,q)if(v[i][2]==0)if(heigou(v[i][0],v[i][1]))cnt--;
    rep(i,q)if(v[i][2])if(same(v[i][0],v[i][1]))dame("No");
    YesNo(m<=n-cnt+cnt*(cnt-1)/2);
}

Measured memory_bytes: 8064
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
typedef int64_t Int;
typedef pair<Int,Int> p;
const Int MOD = 1e9+7;

Int power(Int a, Int n){
    if(a == 0) return 0;
    if(n == 0) return 1;
    
    Int res = 1;
    while(n > 0){
        if(n % 2 == 1) res = res * a % MOD;
        a = a * a % MOD; n /= 2;
    }
    return res;
}

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

    map<p,p> M;
    Int zero_iwashi_count = 0;

    rep(i,N){
        Int A, B; cin >> A >> B;
        if(A == 0 && B == 0){
            zero_iwashi_count++;
            continue;
        } else if (A == 0){
            B = 1;
        } else if (B == 0){
            A = 1;
        } else {
            Int g = __gcd(abs(A),abs(B));
            A /= g; B /= g;
            if(A < 0) {A = -A; B = -B;}
        }

        if(B > 0) M[p(A,B)].first++;
        else M[p(-B,A)].second++;
    }

    Int ans = 1;
    for(auto x : M){
        Int X = x.second.first, Y = x.second.second;

        //cout << X << " " << Y << endl;

        Int now = (power(2,X) + power(2,Y) - 1) % MOD;
        ans = (ans * now) % MOD;
    }

    cout <<  (ans + zero_iwashi_count - 1 + MOD) % MOD << endl;
}


Measured memory_bytes: 19104
//! ----------------------------------------------
//! Framework <https://github.com/vain0x/procon>
//!
//! See the bottom of file for solution.
//! ----------------------------------------------

#![allow(unused_imports)]
#![allow(non_snake_case)]

use std::cell::RefCell;
use std::cmp::{max, min, Ordering};
use std::collections::*;
use std::fmt::{Debug, Display, Formatter, Write as FmtWrite};
use std::io::{stderr, stdin, BufRead, Write};
use std::mem::{replace, swap};
use std::ops::*;
use std::rc::Rc;

/// Print values to standard error if debug mode.
#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), stderr());
            writeln!(err, "\x1B[33m{}\x1B[0m = {:?}", e, $e).unwrap()
        })*
    };
}

/// Read from standard input and parse each word.
/// - `read!(T, U, ..)` parses a line as a tuple of words.
/// - `read![[T]]` parses a line as an array of words.
/// - `read![..; N]` parses `N` lines, using `read!(..)` repeatedly.
#[allow(unused_macros)]
macro_rules! read {
    ([$t:ty] ; $n:expr) =>
        ((0..$n).map(|_| read!([$t])).collect::<Vec<_>>());
    ($($t:ty),+ ; $n:expr) =>
        ((0..$n).map(|_| read!($($t),+)).collect::<Vec<_>>());
    ([$t:ty]) =>
        (rl().split_whitespace().map(|w| w.parse().unwrap()).collect::<Vec<$t>>());
    ($($t:ty),*) => {{
        let buf = rl();
        let mut w = buf.split_whitespace();
        ($(w.next().unwrap().parse::<$t>().unwrap()),*)
    }};
}

/// Read a line from standard input.
#[allow(dead_code)]
fn rl() -> String {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();

    #[allow(deprecated)]
    buf.trim_right().to_owned()
}

// -----------------------------------------------
// Solution
// -----------------------------------------------

fn main() {
    let (A, B, C) = read!(i64, i64, i64);

    let  ok = (1..B + 1).any(|x| x * A % B == C);

    println!("{}", if ok { "YES" } else { "NO" })
}


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

vector<vector<int>> v(200001);
bitset<200001> seen;
bitset<200001> sg;

int f (int x, bool y = true) {
    if (y) {
        seen.set();
        y = false;
    } 
    seen[x] = false;
    sg[x] = false;
    int res = 1;
    for (int i = 0; i < v[x].size(); i++) {
        int tmp = v[x][i];
        if (seen[tmp]) {
            res += f (tmp, y);
            sg[tmp] = false;
        }
    }
    return res;
}

int main() {
    sg.set();
    int n, m, a, b;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (sg[i]) ans = max (ans, f(i));
    }
    cout << ans << endl;
}

Measured memory_bytes: 29712
import sys
input = sys.stdin.readline

from collections import deque

n,m = map(int, input().split())
qp = [tuple(map(int, input().split())) for _ in range(m)]

qp.sort(key=lambda x:x[1])

qp = deque(qp)

ans = 0
pre = 0

while qp:
    a,b = qp.popleft()
    if pre<a:
        ans += 1
        pre = b-1
print(ans)

Measured memory_bytes: 18504
from itertools import permutations


def floyd_warshall(dist):
    v = len(dist)
    for k in range(v):
        for i in range(v):
            for j in range(v):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])


N, M, R = map(int, input().split())
r = list(map(lambda x: int(x)-1, input().split()))
dist = [[float('inf')] * N for _ in range(N)]
for i in range(N):
    dist[i][i] = 0
for _ in range(M):
    A, B, C = map(int, input().split())
    A -= 1
    B -= 1
    dist[A][B] = dist[B][A] = C
floyd_warshall(dist)
ans = float('inf')
for perm in permutations(r):
    d = 0
    for i in range(R-1):
        d += dist[perm[i]][perm[i+1]]
    ans = min(ans, d)
print(ans)


Measured memory_bytes: 59480