akhauriyash/Code-Regression huggingface dataset:
//   _/                _/                 _/_/_/   _/
//_/_/_/_/   _/_/   _/_/_/_/   _/_/    _/       _/_/
// _/     _/    _/   _/     _/    _/  _/_/_/     _/
//_/     _/    _/   _/     _/    _/  _/    _/   _/
// _/_/   _/_/       _/_/   _/_/      _/_/     _/
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const double pi=3.14159265358979323846;
const int inf=1e9;
const ll INF=5e18;
typedef pair<int,int> P;
int main() {
  cin.tie(0),cout.tie(0);
  ios::sync_with_stdio(false);
  ll n,l,a[100005]={},pos,f=1;
  cin >> n >> l;
  for(int i=0; i<n; i++) {
    cin >> a[i];
  }
  for(int i=0; i<n-1; i++) {
    if(a[i]+a[i+1]>=l) {
      f=0;
      pos=i+1;
      break;
    }
  }
  if(f) {
    cout << "Impossible" << endl;
    return 0;
  }
  cout << "Possible" << endl;
  for(int i=1; i<pos; i++) {
    cout << i << endl;
  }
  for(int i=n-1; i>=pos; i--) {
    cout << i << endl;
  }
}

Measured memory_bytes: 1664
n = int(input())
a = list(map(int, input().split()))
# 除かずに数える
cnt = {}
for i in a:
  cnt[i] = cnt.get(i, 0) + 1
ans = 0
for i in cnt.values():
  ans += i * (i - 1) // 2
for i in a:
  # i を除くと cnt[i] - 1 個減る
  print(ans - cnt[i] + 1)

Measured memory_bytes: 26140
#include <bits/stdc++.h>
#define PI                acos(-1)
#define pb                push_back
#define mp                make_pair
#define all(a)            (a).begin(), (a).end()
#define clr(a,h)          memset(a, (h), sizeof(a))
#define F first
#define S second
int faster_in(){int r=0,c;for(c=getchar();c<=32;c=getchar());if(c=='-') return -faster_in();for(;c>32;r=(r<<1)+(r<<3)+c-'0',c=getchar());return r;}

using namespace std;

const int INF = int(1e9 + 7);
typedef long long       ll;
typedef pair<int, int>  ii;
typedef vector<int>     vi;
typedef vector<ii>      vii;
typedef vector<ll>      vll;

int n, v[100010];

map<int, int> cnt[2];

int main()
{
    std::ios::sync_with_stdio(false); cin.tie(0);
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    cin >> n;
    for (int i = 0; i < n; i++)
    {
    	cin >> v[i];
    	cnt[i%2][ v[i] ]++;
    }
    vector<ii> evenVals, oddVals;

    for (auto it : cnt[0])
    {
    	ii val = mp( it.S, it.F );
    	evenVals.pb( val );
    }

    for (auto it : cnt[1])
    {
    	ii val = mp( it.S, it.F );
    	oddVals.pb( val );
    }

    sort( evenVals.rbegin(), evenVals.rend() );
    sort( oddVals.rbegin(), oddVals.rend() );

    int evenUsed = evenVals[0].F, oddUsed = oddVals[0].F;

    if ( evenVals[0].S == oddVals[0].S )
    {
    	if (evenVals.size() == 1)
    	{
    		if (oddVals.size() == 1)
    		{
    			cout << n/2 << '\n';
    			return 0;
    		}
    		oddUsed = oddVals[1].F;
    	}
    	else if (oddVals.size() == 1)
    	{
    		evenUsed = evenVals[1].F;
    	}
    	else 
    	{
    		oddUsed = 0;
    		evenUsed = max( evenVals[0].F + oddVals[1].F, evenVals[1].F + oddVals[0].F );
    	}
    }
    cout << n - ( evenUsed + oddUsed ) << '\n';

    return 0;
}
// PLUS ULTRA!

Measured memory_bytes: 6524
#!/usr/bin/env python3


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    # Failed to predict input format
    x = input()
    if x.isupper():
        print('A')
    else:
        print('a')
    pass

if __name__ == '__main__':
    main()


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

int main() {
    int n;
    ll T;
    cin >> n >> T;
    vector<ll> t(n);
    rep(i,n) cin >> t[i];
    ll ans= 0;
    for(int i = 1; i < n; ++i) {
        ans+=min(T,t[i]-t[i-1]);
    }
    ans+=T;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4636
D=int(input())
c=list(map(int,input().split()))
s=[list(map(int,input().split())) for _ in range(D)]

last=[0]*26


for d in range(1,D+1):
    ans=[]
    for choice in range(1,27):
        ans_tmp=0
        ans_tmp+=s[d-1][choice-1]
        for i in range(26):
            if i+1==choice:
                continue
            ans_tmp-=c[i]*(d-last[i])*max(2,(D-d)//36)
        ans.append((ans_tmp,choice))
    _,case=max(ans)
    last[case-1]=d
    print(case)



Measured memory_bytes: 9300
import math
n = int(input())

prime = []
x = 1
while len(prime) < 55:
    if_prime = 10 * x + 1
    flag = True
    for j in range(2, int(math.sqrt(if_prime)) + 1):
        if if_prime % j == 0:
            flag = False
            break
    if flag == True:
        prime.append(if_prime)
    x = x + 1
for i in range(n):
    print(prime[i], end=" ")

Measured memory_bytes: 3060
m[300][300];main(n,i,j,k,M){for(;scanf("%d",&n),n;printf("%d\n",M)){
for(getchar(),i=1;i<=n;m[j][i]=0,getchar(),i++)for(j=1;j<=n;j++)m[j][i]=getchar()-'0';
for(j=1;j<=n+1;j++)m[j][i]=0;
for(M=0,i=1;i<=n;i++)for(j=1;j<=n;j++)if(m[i][j]){
	for(k=1;;k++)if(!m[i+k][j])break;if(M<k)M=k;
	for(k=1;;k++)if(!m[i][j+k])break;if(M<k)M=k;
	for(k=1;;k++)if(!m[i+k][j+k])break;if(M<k)M=k;
	for(k=1;;k++)if(!m[i-k][j+k])break;if(M<k)M=k;
}
}exit(0);}

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

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;cin >> n;
	vector<int> a(n),b(n),c(n);
	rep(i,n) cin >> a.at(i) >> b.at(i) >> c.at(i);
	vector<vector<int>> dp(n+1,vector<int>(3));
	for(int i=1;i<=n;++i){
		dp[i][0]=max(dp[i-1][1]+a.at(i-1),dp[i-1][2]+a.at(i-1));
		dp[i][1]=max(dp[i-1][0]+b.at(i-1),dp[i-1][2]+b.at(i-1));
		dp[i][2]=max(dp[i-1][0]+c.at(i-1),dp[i-1][1]+c.at(i-1));
	}
	cout << max(dp[n][0],max(dp[n][1],dp[n][2])) << endl;
}

Measured memory_bytes: 6912
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define ALL(x) (x).begin(), (x).end()
#define REP(i ,n) for(int i = 0; i < (int)(n); i++)
#define pb push_back
typedef vector<int>vint;
typedef vector<ll>vll;
template<typename T> istream &operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
template<typename A,typename B>inline bool chmin(A &a,const B &b){if(a>b){a=b;return true;}else{return false;}}
template<typename A,typename B>inline bool chmax(A &a,const B &b){if(a<b){a=b;return true;}else{return false;}}

int main()
{
    int N,K;
    cin >> N >> K;
    vint A(N);
    cin >> A;
    int ans = 1;
    N -= K;
    K--;
    ans += N/K;
    N %= K;
    if(N)ans++;
    cout << ans << endl;
}

Measured memory_bytes: 3752
#!/usr/bin/env python3
#ABC95 D

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,c = LI()
xv = [LI() for _ in range(n)]

l1 = [v for x,v in xv]
l2 = l1[:]
r1 = l1[::-1]
r2 = r1[:]

l1 = list(accumulate(l1))
l2 = list(accumulate(l2))
r1 = list(accumulate(r1))
r2 = list(accumulate(r2))

for i,(x,v) in enumerate(xv):
    l1[i] -= x
    l2[i] -= 2*x
    r1[-i-1] -= c - x
    r2[-i-1] -= 2*(c - x)

for i in range(1,n):
    l1[i] = max(l1[i],l1[i-1])
    r1[i] = max(r1[i],r1[i-1])

ans = max(l1[-1],r1[-1])
for i in range(n-1):
    ans = max(ans,l2[i] + r1[-i-2])
    ans = max(ans,r2[i] + l1[-i-2])
print(max(0,ans))

Measured memory_bytes: 84956
#include <iostream>
using namespace std;
int a,b;
int main() {
    cin >> a >> b;
    if(a > 0) {
        cout << "Positive" << endl;
        return 0;
    }
    if(a <= 0 && b >= 0) {
        cout << "Zero" << endl;
        return 0;
    }
    if((b-a-1)%2==0) {
        cout << "Positive" << endl;
    } else {
        cout << "Negative" << endl;
    }
    return 0;
}


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

using namespace std;
 
#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

typedef int64_t ll; typedef vector<int> VI; typedef pair<int,int> pii;
const ll mod = 1e9+7;

void dbg(){ cerr << "\n"; }  
template <typename T,typename ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }

int main()
{
 
	//cin.tie(0); ios_base::sync_with_stdio(false);
	
	int n, y;
	cin >>n >>y;
	
	rep(i, y/10000+1) rep(j, y/5000+1){
		int zi = n - i -j;
		if( zi >=0 && 10000*i + 5000*j + 1000*zi == y){
			cout << i <<" "<< j <<" "<< zi <<endl;
			return 0;
		}
	}
	puts("-1 -1 -1");
	return 0;
}


Measured memory_bytes: 256
// In the name of Allah
// #Isart

#include<bits/stdc++.h>

#define pii pair<int, int>
#define pb push_back
#define F first
#define S second
#define ll long long
#define ld long double

using namespace std;

const int MAXN = 1e5 + 10;
int r, c, n;
vector<pii> d[4];
vector<int> v;
bool mark[MAXN];

bool check(int x, int y){
	int cnt = 0;
	if(x == 0 or x == r) cnt ++;
	if(y == 0 or y == c) cnt ++;
	if(cnt > 0) return true;
	else return false;
}

void add(int x, int y, int id){
	if(x == 0)		d[0].pb({y, id});
	else if(y == c) d[1].pb({x, id});
	else if(x == r) d[2].pb({y, id});
	else if(y == 0) d[3].pb({x, id});
	return;
}

int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> r >> c >> n;
	for(int i = 0; i < n; i ++){
		int a, b, c, d; cin >> a >> b >> c >> d;
		if(check(a, b) and check(c, d)){
			add(a, b, i);
			add(c, d, i);
		}
	}
	for(int i = 0; i < 4; i ++){
		sort(d[i].begin(), d[i].end());
		if(i > 1) reverse(d[i].begin(), d[i].end());
		for(auto u : d[i]){
			if(mark[u.S] == true){
				if(v.back() == u.S)v.pop_back();
			}
			else{
				mark[u.S] = true;
				v.pb(u.S);
			}
		}
	}
	if(v.size() == 0)
		cout << "YES" << endl;
	else 
		cout << "NO" << endl;
	return 0;	
}

Measured memory_bytes: 2520
awk 'function mo(x){
  x = int(x)
  return 1 <= x && x <= 12
}
{
  head = substr($1, 1, 2)
  tail = substr($1, 3, 2)
  print (mo(head) && mo(tail)) ? "AMBIGUOUS" : (!mo(head) && !mo(tail)) ? "NA" : (mo(head) && !mo(tail)) ? "MMYY" : "YYMM"
}'


Measured memory_bytes: 552
n, m, q = list(map(int, input().split()))
abcd = [list(map(int, input().split())) for _ in range(q)]

import itertools
anses = []
# for A in itertools.product(sum(([i]*n for i in range(1,m+1)),[]), repeat=n):
# for A in itertools.product(range(1, m + 1), repeat=n):

def f(A):
  for ai in range(A[-1], m + 1):
    if len(A) < n:
      f(A + [ai])
    else:
      p = 0
      for a, b, c, d in abcd:
        a -= 1
        b -= 1
        if A[b] - A[a] == c:
          p += d
      anses.append(p)

f([1])
print(max(anses))


Measured memory_bytes: 12756
let [| A; B |] = stdin.ReadLine().Split(" ") |> Array.map int

let rec solve rest num = 
  if rest <= 0 then 
    num 
  else
    solve (rest - A + 1) (num + 1)

(if B = 1 then 0 else solve (B - A) 1) |> printfn "%d"

Measured memory_bytes: 30020
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<cstdlib>

using namespace std;

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

    unsigned long long a[n];
    for(int i=0;i<n;i++)cin >> a[i];

    vector<unsigned long long> range;

    sort(a, a+n, greater<unsigned long long>());

    for(int i=0;i<n-1;i++){
        if(a[i]==a[i+1]){
            range.push_back(a[i]);
            i++;
        }
        if(range.size()>2)break;
    }
//for(int i=0;i<range.size();i++)cout << "#" << range[i];
    if(range.size()<2)cout << 0 << endl;
    else cout << range[0] * range[1] << endl;;
}


Measured memory_bytes: 1024
#include <iostream>

using namespace std;

int main(){
	int owan, koho[50];
	int n, i ,p;

	while (cin >> n >> p){							//????£????&?°????'s ??°

		if (n == 0 && p == 0){						//????????????
			break;
		}

		for (i = 0; i < 50; i++){					//????????????????????¢??¬
			koho[i] = 0;
		}

		owan = p;

		for (i = 0;; i = (i + 1) % n){				//????£??????°??§?????????????¶????????????????

			if (owan == 0){							//?°???????????????????
				owan = koho[i];						//????????£??????????????????????????£???
				koho[i] = 0;
			}else{									//?°???????????????????
				owan--;								//????????£??????????????????????????£???(?????????)
				koho[i]++;							//???????¢?????????????

				if (owan == 0 && p == koho[i]){		//???????????£???&????????¨??¨?????£??????
					cout << i << endl;
					break;

				}
			}
		}
	}
	return 0;
}

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

using namespace std;
using ll = long long;

int main() {
    int N = 0;
    int K;
    cin >> N;
    cin >> K;
    vector<int> A(N,0);
    
    
    for(int i = 0; i < N; i++) {
        int n;
        cin >> n;
        A.at(n - 1)++;
    }
    sort(A.begin(),A.end());
    queue<int> q;
    for(int i = 0; i < N; i++) {
        if(A.at(i)) {
            q.push(A.at(i));
            //cout << A.at(i) << endl;
        }
    }
    int ans = 0;
    int s = q.size();
    for(int i = 0; i < s - K; i++) {
        ans += q.front();
        q.pop();
    }

    cout << ans << endl;


    return 0;
}

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

signed main() {
	int N;
	cin>>N;
	int a;
	int ans=0;
	for(int i=0;i<N;i++){
		cin>>a;
		while(a%2==0){
			a/=2;
			ans++;
		}
	}
	cout<<ans<<endl;
}





Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <deque>
#define N 101000
template<typename T> inline void read(T &x) {
	x = 0; char c = getchar(); bool flag = false;
	while (!isdigit(c)) {if (c == '-') flag = true; c = getchar(); }
	while (isdigit(c)) {x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); }
	if (flag)	x = -x;
}
using namespace std;
int n;
int dis[N];
deque<int> q, qq;
inline void bfs() {
	q.push_back(1);
	qq.push_back(1);
	while (q.size()) {
		int p = q.front();
		q.pop_front();
		int v = qq.front();
		qq.pop_front();
		if (dis[p])	continue;
		dis[p] = v;
		if (!p)	return ;
		q.push_back((p + 1) % n);
		qq.push_back(dis[p] + 1);
		q.push_front(p * 10 % n);
		qq.push_front(dis[p]);
	}
}

int main() {
	read(n);
	bfs();
	printf("%d\n", dis[0]);
	return 0;
}
/*
6 3
41 5
79992 36
7 2(1001)
*/

Measured memory_bytes: 1408
#include<bits/stdc++.h>
#define ll long long
#define MOD = 1e9+7
#define rep(i,n) for(int i=0;i<(n);++i)
const double PI=3.14159265358979323846; 
const int INF = 1001001001;
using namespace std;

int main(){
  int x;
  rep(i,5){
    cin >> x; 
    if(x == 0){
      cout << i+1 << endl;
      return 0;
    }
  }
}

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

int main(){
    int A,B,K;
    cin >> A >> B >> K;
    int t=min(A,B),cnt=0;
    while(cnt<K){
        if(A%t==0 && B%t==0) cnt+=1, t-=1;
        else t-=1;
    }
    cout << t+1 << endl; 
}





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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define eb emplace_back

typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;

void Main()
{
	int l;
	cin >> l;
	double x = double(l)/3.0;
  	cout << (double)x*x*x << endl;
    return;
}

int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
	return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main  {
   public static void main(String[] args)  {
      Scanner sc = new Scanner(System.in);
      
      
      long a = sc.nextLong();
      long b = sc.nextLong();
      long c = sc.nextLong();
      long k = sc.nextLong();
                
      if (a > k) {
         System.out.println(k);
      } else if (a == k) {
         System.out.println(a);
      } else {
         if (b >= (k - a)) {
            System.out.println(a);
         } else {
            System.out.println(a - (k - (a + b)));
         }
      }      
   }
}

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

int main() {
  ll N = 0,K = 0;
  cin >> N >> K;
  vector<ll>A(N);
  rep(i,N){
    cin >> A[i];
  }
  rep(i,N-K){
    if(A[i] < A[i + K]){
      cout << "Yes" << endl;
    }
    else{
      cout << "No" << endl;
    }
  }
}

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

using i32 = int_fast32_t;
using i64 = int_fast64_t;
using u32 = uint_fast32_t;
using u64 = uint_fast64_t;
using f64 = double;
using f80 = long double;

#define FOR(v, a, b) for(i64 v = (a); v < (b); ++v)
#define FORE(v, a, b) for(i64 v = (a); v <= (b); ++v)
#define REP(v, n) FOR(v, 0, n)
#define REPE(v, n) FORE(v, 0, n)
#define REV(v, a, b) for(i64 v = (a); v >= (b); --v)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define ITR(it, c) for(auto it = (c).begin(); it != (c).end(); ++it)
#define RITR(it, c) for(auto it = (c).rbegin(); it != (c).rend(); ++it)
#define EXIST(c,x) ((c).find(x) != (c).end())
#define fst first
#define snd second
#define UNIQ(v) (v).erase(unique(ALL(v)), (v).end())
#define bit(i) (1LL<<(i))

#ifdef DEBUG
#include <Mylib/Debug/debug.cpp>
#else
#define dump(...) ((void)0)
#endif

using namespace std;

template <typename I> void join(ostream &ost, I s, I t, string d=" "){for(auto i=s; i!=t; ++i){if(i!=s)ost<<d; ost<<*i;}ost<<endl;}
template <typename T> istream& operator>>(istream &is, vector<T> &v){for(auto &a : v) is >> a; return is;}
template <typename T> void pout(const T &value){std::cout << value << "\n";}
template <typename T, typename ...Args> void pout(const T &value, const Args&... args){std::cout << value << " ";pout(args...);}

template <typename T, typename U> bool chmin(T &a, const U &b){return (a>b ? a=b, true : false);}
template <typename T, typename U> bool chmax(T &a, const U &b){return (a<b ? a=b, true : false);}
template <typename T, size_t N, typename U> void fill_array(T (&a)[N], const U &v){fill((U*)a, (U*)(a+N), v);}
template <typename T> auto make_vector(int n, int m, const T &value){return vector<vector<T>>(n, vector<T>(m, value));}


struct Init{
  Init(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(12);
    cerr << fixed << setprecision(12);
  }
}init;



int main(){
  string s, t;

  while(cin >> s >> t){
    t.pop_back();

    pout(s == t ? "Yes" : "No");
  }    

  return 0;
}


Measured memory_bytes: 3652
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
char T[1010], S[1010];
int main(){
	scanf("%s%s", S, T);
	int Ans = 1000010;
	int l1 = strlen(S), l2 = strlen(T);
	for(int i = 0 ; i <= l1 - l2 ; i++){
		int cnt = 0;
		for(int j = 0 ; j < l2 ; j++){
			int k = i + j;
			if(S[k] != T[j]) cnt++;
		}
		Ans = min(Ans, cnt);
	}
	printf("%d", Ans);
	return 0;
}

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

#define ll long long
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rep(i,n) for(int i = 0; i < int(n); i++)

#define MAX(a,b) (a > b ? a : b)
#define MIN(a,b) (a < b ? a : b)
const int MOD = 1000000007;

int n;
int matrix[21][21];
ll dp[21][2097159];

ll fun(int i, int num) {
    if(i == n) {
        if(num == (1 << n) - 1) return 1;
        return 0;
    }
    if(dp[i][num] != -1) return dp[i][num];
    ll ans = 0;
    for(int j = 0; j < n; j++) {
        if(matrix[i][j] && !(num & (1 << j))) {
            ans += fun(i + 1, (num | (1 << j)));
            ans %= MOD;
        }
    }
    return dp[i][num] = ans;
}

int main() {
    IOS;
    memset(dp, -1, sizeof(dp));
    cin >> n;
    rep(i, n) rep(j, n) cin >> matrix[i][j];
    cout << fun(0, 0);
    return 0;
}

Measured memory_bytes: 344448
import bisect

N = int(input())
A = [0] * N
for i in range(N):
  A[i] = int(input())

B = [A[N - 1]]
for i in reversed(range(0, N - 1)):
  if A[i] >= B[-1]:
    B.append(A[i])
  else:
    index = bisect.bisect_right(B, A[i])
    B[index] = A[i]
print(len(B))

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

// iterator
#define REP(i,init, n) for(lli i=init;i<n;i++)
#define REPE(i,init, n) for(lli i=init;i<=n;i++)
#define REPIT(it,container) for(auto it = container.begin(); it != container.end(); it++)
#define REPIT_R(it,container) for(auto it = container.rbegin(); it != container.rend(); it++)

// input
#define cin1(x)             cin >> x
#define cin2(x, y)          cin >> x >> y
#define cin3(x, y, z)       cin >> x >> y >> z
#define ncin1(n, x)         REP(i, 0, n) {cin1(x[i]);}
#define ncin2(n, x, y)      REP(i, 0, n) {cin2(x[i], y[i]);}
#define ncin3(n, x, y, z)   REP(i, 0, n) {cin3(x[i], y[i], z[i]);}

// output
#define cout1(x)         cout << #x << ": " << x << endl;
#define ncout1(n, x)     REP(i, 0, n) {cout << #x << "[" << i << "]: "<< x[i] << endl;}

// sort
#define sort_r(x, y)        sort(x, y, greater<lli>()); // 降順(5,4,3,,,)

#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))

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

struct edge {
    lli to;
    lli cost;
};

vector<edge> G[100001];
lli d[100001];
lli n;
lli prev_v[100001]; // 経路復元用

void dijkstra(lli start) {
    REPE(i, 1, n) {
        d[i] = LLONG_MAX;
    }
    d[start] = 0;
    prev_v[start] = start;

    // first がその時点での最短経路のコスト、second が頂点の番号
    priority_queue<P, vector<P>, greater<P>> que;
    que.push(P(0, start));

    while (!que.empty()) {
        P p = que.top();
        que.pop();

        lli cur_v = p.second;
        // もっと短い経路が既に登録されていたら、このpopしたやつは無視してよい
        if (d[cur_v] < p.first) {
            continue;
        }
        // cur_v の辺を周って、更新しつつ queue に push していく
        REP(i, 0, (lli)G[cur_v].size()) {
            edge e = G[cur_v][i];
            if (d[e.to] > d[cur_v] + e.cost) {
                d[e.to] = d[cur_v] + e.cost;
                que.push(P(d[e.to], e.to));
                prev_v[e.to] = cur_v;
            }
        }
    }
}

int main() {
    cin1(n);
    REP(i, 0, n-1) {
        lli a, b, c;
        cin >> a >> b >> c;
        edge e1 = {b, c};
        edge e2 = {a, c};
        G[a].push_back(e1);
        G[b].push_back(e2);
    }
    lli q, k;
    cin2(q, k);
    lli x[q], y[q];
    ncin2(q, x, y);

    dijkstra(k);
    REP(i, 0, q) {
        cout << d[x[i]] + d[y[i]] << endl;
    }



}


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

int main(){
  int a, b;
  cin >> a >> b;
  
  int ans = 0;	// 使うタップ数
  int noused = 1;	// 未使用数
  
  /*
    1:4 = a
    2:7 = 2a - 1
    3:10 = 3a -2
    4:13 = 4a - 3 = 3(a-1) + a
    5:16 = 5a -4 = 4(a-1)+a
   */
  while(noused < b){
    --noused;
    noused += a;
    ++ans;
  }
  
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 3620
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		String aCards = sc.nextLine();
		String bCards = sc.nextLine();
		String cCards = sc.nextLine();
		
		int nowTurn = 0; // Aさんから開始する
		int aCardNum = 0;
		int bCardNum = 0;
		int cCardNum = 0;
		int aCardMaxLen = aCards.length();
		int bCardMaxLen = bCards.length();
		int cCardMaxLen = cCards.length();
		
		
		char nowChar = 'z'; // 初期化
		
		// 結果が出るまで続ける
		while(true) {
			if(nowTurn == 0) {
				if (aCardNum >= aCardMaxLen) break; // 上がり
				nowChar = aCards.charAt(aCardNum);
				aCardNum++;
			} else if(nowTurn == 1) {
				if (bCardNum >= bCardMaxLen) break; // 上がり
				nowChar = bCards.charAt(bCardNum);
				bCardNum++;
			} else if (nowTurn == 2) {
				if (cCardNum >= cCardMaxLen) break; // 上がり
				nowChar = cCards.charAt(cCardNum);
				cCardNum++;
			}
			
			// 次の番を決める
			if ('a' == nowChar) {
				nowTurn = 0;
			} else if ('b' == nowChar) {
				nowTurn = 1;
			} else if ('c' == nowChar) {
				nowTurn = 2;
			}
		}
		
		// 勝者を表示
		System.out.println((char)('A' + nowTurn));
	}

}


Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0);cin.tie(0)
int main(){
    IO;
    int dtas,num[100000],ct=0;
    cin>>dtas;
    for(int i=0;i<dtas;i++) cin>>num[i];
    for(int i=0;i<dtas;i+=2){
        //if(num[i]==1) ct++;
        if(num[i]%2==1){
            ct++;
            //cout<<num[i]<<" ";
        }
    }
    cout<<ct<<"\n";
}


Measured memory_bytes: 3612
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<string>

using namespace std;

int Base10toN(int k, int n) {
   
   string str;
   int count = 0;
   while (k > 0) {
      str = to_string(k % n) + str;
      count += k % n;
      k /= n;
   }
   // return stoi(str);
   return count;
}

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

   for (int i = 0; i <= N; i++) {
      int count = 0;
      count += Base10toN(i, 6);
      count += Base10toN(N - i, 9);
      if (ans > count) ans = count;
   }
   cout << ans << endl;
   return 0;
}


Measured memory_bytes: 256
//D
//Author : Sidiq Tri Pratikto
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define all(v) v.begin(), v.end()

using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> new_data_set;
//order_of_key(x) = number of elements stricly smaller than x
//find_by_order(x) = return x-th largest element
typedef long long LL;
const LL MOD = 1e9 + 7;
const double PI = 2 * acos(0);

int main() {
	int x;
	LL awal = 0;
	scanf("%d", &x);
	while (1) {
		bool neg = 0;
		LL cnt = (awal * awal * awal * awal * awal) - x;
		if (cnt < 0) neg = 1, cnt = -cnt;
		LL tmp = cnt;
		bool cek = 1;
		vector<pair<int, int> > prim;
		for (int i = 2; i <= sqrt(cnt); i++) {
			int z = 0;
			while (tmp % i == 0) {
				z++;
				tmp /= i;
			}
			if (z / 5 > 0) prim.pb(mp(i, z / 5));
			if (z % 5 != 0) {
				cek = 0;
				break;
			}
		}
		if (tmp > 1) cek = 0;
		if (cek) {
			LL B = 1;
			if (neg) B = -1;
			for (auto i : prim) {
				for (int j = 0; j < i.se; j++) {
					B *= i.fi;
				}
			}
			printf("%lld %lld\n", awal, B);
			return 0;
		}
		awal++;
	}
}

Measured memory_bytes: 3872
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String args[]) throws Exception{
        BufferedReader stdR = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(stdR.readLine());
        int[] a = new int[N];
        for(int i = 0 ; i < N ; i++) {
            a[i] = Integer.parseInt(stdR.readLine());
        }
        Arrays.sort(a);
        int count = 0;
        int num = 0;
        for(int i = 0 ; i < N ; i++) {
            if(num != a[i])count++;
            num = a[i];
        }
        System.out.println(count);
    }
}


Measured memory_bytes: 22484
# encoding:utf-8
import copy
import numpy as np
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import math


N = int(input())
H = [int(i) for i in input().split()]


max_h = [-1 for i in range(N)]
max_h[0] = H[0]
for i in range(1,N):
    max_h[i] = max(max_h[i-1],H[i])
    
ans = 0
for i in range(N):
    if H[i] >= max_h[i]:
        ans += 1
print(ans)

"""
ans = 0
for i in range(N):
    base = H[i]
    check = True
    for j in range(N):
        if i<=j:
            pass
        else:
            if H[i]>=H[j]:
                pass
            else:
                check = False
                break
    if check:
        ans += 1
print(ans)
"""


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

int n, a;
set <int> st;

int main() {
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> a;
        st.insert(a);
    }
    if (st.size() == n) cout << "YES\n";
    else cout << "NO\n";
}


Measured memory_bytes: 9600
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
using in = int64_t;
#define rep(i, n) for (in i = 0; i < (in)(n); i++)
#define REP(i,a,b) for(in i=(in)(a);i<(in)(b);i++)
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
const double PI=3.14159265358979323846;
const in MOD = 1000000007;
const in INF=1e18+7;
const in inf=1e9+7;
using P=pair<in,in>;
vector<in> dx={0,1,-1,0};
vector<in> dy={1,0,0,-1};

vector<in> yakusu(in n){//約数の全列挙
    vector<in> ret(0);
    for(in i=1;i*i<=n;i ++){
        if(n%i==0){
            ret.emplace_back(i);
            if(i*i<n) ret.emplace_back(n/i);
        }
    }
    return ret;
}

int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cout << fixed << setprecision(10);
    in n;
    cin>>n;
    auto a=yakusu(n);
    in ans=0ll;
    for(auto x:a){
        in y=n/x-1ll;
        if(x<y) ans +=y;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 384
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>	
#include <time.h>
#include <vector>
#include <stdio.h>
#include <memory.h>
#include <string>
#include <string.h>
#include <map>
#include <algorithm>
#include <queue>
#include <set>
#include <time.h>
#include <assert.h>
#include <sstream>
//#include <unordered_map>
#include <bitset>
#include <utility>
#include <iomanip>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <numeric>
#include <math.h>
#include <cmath>
#include <complex>
#ifdef MYDEF
#include "inc.h"
#endif
using namespace std;
typedef long long ll;
typedef complex<double> point;


int main() {
#ifdef MYDEF
	// sandstone
	HEAD
		freopen("a.txt", "r", stdin);
	//freopen("a.txt", "w", stdout);
	decTime;
#endif

	char s[20];
	scanf("%s", s);
	int n = strlen(s);
	if(n == 1)
		return 0 * printf("%d\n", s[0] - '0');
	int sum = 0, r = 0;
	for(int i = 0; i < n; ++i)
		r += s[i] - '0';
	if(s[0] == '1') {
		for(int i = 1; i < n && s[i] == '0'; ++i)
			s[i] = '9';
		sum = 9;
		--s[1], sum = s[0] + s[1] - 2 * '0';
	}
	else
		--s[0], sum = s[0] - '0' + 9;
	for(int i = 2; i < n; ++i)
		sum += 9;
	printf("%d\n", max(sum, r));


#ifdef MYDEF
	printTime;
#endif
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
	int N;
	long long A, B;
	cin >> N >> A >> B;
	vector<int> X(N);
	for (auto& x : X) cin >> x;
	long long r = 0;
	for (int i = 1; i < N; ++ i) {
		r += min(B, (X[i] - X[i-1]) * A);
	}
	cout << r << endl;
}


Measured memory_bytes: 640
N,K = map(int,input().split())
class Combination(): # nCr mod MOD など
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(10**6)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.fac, self.facinv = self.prepare(n_max)
        #self.modinv = self.make_modinv_list(n_max) ##なくても問題ないので、必要な時のみ使う
        
    def prepare(self,n): # 前処理(コンストラクタで自動的に実行)
        # 1! ~ n! の計算
        factorials = [1]  # 0!の分
        for m in range(1, n+1):
            factorials.append(factorials[m-1]*m%self.mod)
        # n!^-1 ~ 1!^-1 の計算
        invs = [1] * (n+1)
        invs[n] = pow(factorials[n], self.mod-2, self.mod)
        for m in range(n, 1, -1):
            invs[m-1] = invs[m]*m%self.mod
        return factorials, invs # list
    
    def make_modinv_list(self, n): # 0からnまでのmod逆元のリストを返す O(n)
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            # 整数aのMを法とした時の逆元a^-1は、(0<=a<=M-1)
            # a == qM+rであるとき(qは商,rは余り)、
            # a^-1 == -qr^-1 % M で与えられる。
            modinv[i] = (self.mod - self.mod//i)*modinv[self.mod%i]  % self.mod
        return modinv

    def perm_mod(self,n,r): # nPr % self.mod
        if n < r:
            return 0
        if (n < 0 or r < 0):
            return 0
        return (self.fac[n] * self.facinv[n-r]) % self.mod

        
    def combi_mod(self,n,r): # nCr % self.mod
        if n < r:
            return 0
        if (n < 0 or r < 0):
            return 0
        return (((self.fac[n] * self.facinv[r]) % self.mod) * self.facinv[n-r]) % self.mod

    def repeated_permutation(self,n,deno): # 重複順列
        # n!/(deno[0]!*deno[1]!*...*deno[len(deno)-1]) % MOD
        ## n:int(分子),deno:分母のlist
        if n < max(deno):
            return 0
        if (n < 0 or min(deno) < 0):
            return 0
        D = 1
        for i in range(len(deno)):
            D = D*self.facinv[deno[i]] % self.mod
        return self.fac*D % self.mod # int ## == n!/(deno[0]!*deno[1]!*...*deno[len(deno)-1]) % MOD
    
    def H(self,n,r): # 重複組合せ nHr % self.mod
        now_n = len(self.fac)
        if now_n < n+r-1: # もしself.facの長さが足りなかったら追加
            for i in range(now_n+1, n+r-1+1):
                self.fac.append(self.fac[i-1]*i%self.mod)
        return self.combi_mod(n+r-1,r)

MOD = 10**9+7
C = Combination(N)
for i in range(1,K+1):
    ans = (C.combi_mod(K-1,i-1)*C.combi_mod(N-K+1,i))%MOD
    print(ans)


Measured memory_bytes: 3444
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

S = list(sys.stdin.readline().rstrip())
T = list(sys.stdin.readline().rstrip())
Q = int(sys.stdin.readline())
ABCD = [list(map(int, sys.stdin.readline().split())) for _ in range(Q)]

S = np.array(['.'] + S + ['.'])
T = np.array(['.'] + T + ['.'])

SA = (S == 'A').cumsum()
SB = (S == 'B').cumsum()
TA = (T == 'A').cumsum()
TB = (T == 'B').cumsum()
ans = []
for a, b, c, d in ABCD:
    sa = SA[b] - SA[a - 1]
    sb = SB[b] - SB[a - 1]
    ta = TA[d] - TA[c - 1]
    tb = TB[d] - TB[c - 1]
    ans.append((sa - sb) % 3 == (ta - tb) % 3)

for a in ans:
    if a:
        print('YES')
    else:
        print('NO')


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



bool fun(pair<int,int> a,pair<int,int> b){
    if(a.first == b.first){
        return a.second<b.second;
    }
    return a.first<b.first;
}


ll dist(pair<int,int> a,pair<int,int> b){
    ll ans=abs(a.first-b.first);
    ans+=abs(a.second-b.second);
    return ans;

}



ll mod=1e9 +7;

int main(){

 int n;
 cin>>n;
 vector<pair<ll,ll> >  co;
 for(int i=0;i<n;i++){
    int x,y;
    cin>>x>>y;
    co.push_back({x,y});
 }
 sort(co.begin(),co.end(),fun);
 ll ans=0;
 ll mini= co[0].first+co[0].second;
 for(int i=1;i<n;i++){
    ans=max(ans,co[i].first + co[i].second - mini);
    mini= min(mini,(ll)co[i].first +co[i].second);
 }

 mini = co[0].first - co[0].second;
 for(int i=1;i<n;i++){
    ans=max(ans,co[i].first - co[i].second - mini);
    mini= min(mini,(ll)co[i].first - co[i].second);
 }
 cout<<ans<<endl;


}


Measured memory_bytes: 7440
#include<stdio.h>
#include<ctype.h>
int main(void){
	char a;
	while(1){
		scanf("%c",&a );
		if(a=='\n')break;
		if(islower(a))printf("%c",toupper(a) );
		else printf("%c",tolower(a) );
	}
	printf("\n");
	return 0;
}

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

const int MAX_H = 100;
const int MAX_W = 100;

//输入
int H, W;
char g[MAX_H][MAX_W + 1];

int d[4][2] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};        //方向

//深度优先遍历g[i][j]同类局域
void dfs(int x, int y, int c){
    for(int i = 0; i < 4; i ++){
        int nx = x + d[i][0], ny = y + d[i][1];
        if(0 <= nx && nx < H && 0 <= ny && ny < W && g[nx][ny] == c){
            g[nx][ny] = '1';
            dfs(nx, ny, c);
        }
    }
}

void solve(){
    //遍历果园，每到一个新位置，遍历该位置能到达的地方
    int ans = 0;
    for(int i = 0; i < H; i ++){
        for(int j = 0; j < W; j ++){
            if(g[i][j] != '1'){
                ans ++;
                char c = g[i][j];
                g[i][j] = '1';
                dfs(i, j, c);
            }
        }
    }
    printf("%d\n", ans);
}

int main(int argc, char const *argv[]){

    while(scanf("%d %d", &H, &W)){
        if(H == 0 && W == 0) break;
        for(int i = 0; i < H; i ++){
            scanf("%s", g[i]);
        }
        solve();
    }

    return 0;
}


Measured memory_bytes: 3136
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
#define D10 fixed<<setprecision(10)
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
const int INF = 114514810;
const int MOD = 1000000007;
const double EPS = 1e-10;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }

/*--------------------template--------------------*/


pii place(vector<vi> &v, int p)
{
	int cnt = 0;
	REP(i, v.size())
	{
		if (cnt <= p && p < cnt+v[i].size())
		{
			return pii(i, p - cnt);
		}
		else cnt += v[i].size();
	}
}

vector<vi> copy(vi &from, int s)
{
	vector<vi> to(s);
	REP(i, from.size())
	{
		to[i / s].push_back(from[i]);
	}
	return to;
}

int main()
{
	int n, q;
	cin >> n >> q;
	int s = 1500;
	vi a(n), mn(s);
	REP(i, n) cin >> a[i];
	vector<vi> v = copy(a, s);
	REP(i, v.size()) mn[i] = (v[i].size() > 0 ? *min_element(ALL(v[i])) : INF);
	int cntc = 0;
	REP(op, q)
	{
		if (cntc > s)
		{
			vi tmp;
			REP(i, v.size())REP(j, v[i].size()) tmp.push_back(v[i][j]);
			v = copy(tmp, s);
			REP(i, v.size()) mn[i] = (v[i].size() > 0 ? *min_element(ALL(v[i])) : INF);
			cntc = 0;
		}
		int a, b, c;
		cin >> a >> b >> c;
		if (a == 0)
		{
			int rx = place(v, c).first, ry = place(v, c).second;
			int t = v[rx][ry];
			v[rx].erase(v[rx].begin() + ry);
			int lx = place(v, b).first, ly = place(v, b).second;
			v[lx].insert(v[lx].begin() + ly, t);
			mn[lx] = *min_element(ALL(v[lx]));
			mn[rx] = (v[rx].size() > 0 ? *min_element(ALL(v[rx])) : INF);
			cntc++;
		}
		else if (a == 1)
		{
			int lx = place(v, b).first, ly = place(v, b).second;
			int rx = place(v, c).first, ry = place(v, c).second;
			int ans = INF;
			if (lx == rx) FOR(i, ly, ry + 1) chmin(ans, v[lx][i]);
			else
			{
				FOR(i, ly, v[lx].size()) chmin(ans, v[lx][i]);
				FOR(i, lx + 1, rx) chmin(ans, mn[i]);
				REP(i, ry + 1) chmin(ans, v[rx][i]);
			}
			cout << ans << endl;
		}
		else
		{
			int x = place(v, b).first, y = place(v, b).second;
			v[x][y] = c;
			mn[x] = *min_element(ALL(v[x]));
		}
	}
	return 0;
}

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

int main(){
    using namespace std;
    unsigned long N, K;
    cin >> N >> K;
    constexpr unsigned long MOD = 1000000007;
    cout << (N * (N + 1) + K * (N + 2) - 2 * K * K + 6) % MOD * (N - K + 2) % MOD * 166666668 % MOD << endl;
    return 0;
}

Measured memory_bytes: 3636
let quick_sort (a : (int * char * int) array) cmp =
  let rec partition p r =
    let swap i j = let t = a.(i) in a.(i) <- a.(j); a.(j) <- t
    in
    let rec exchange i j =
      if j >= r then (swap (i + 1) r; i + 1)
      else if cmp a.(j) a.(r) <= 0 then (swap (i + 1) j; exchange (i + 1) (j + 1))
      else exchange i (j + 1)
    in exchange (p - 1) p
  and doit p r =
    if p < r then begin
      let q = partition p r in
      doit p (q - 1);
      doit q r
    end in
  doit 0 (Array.length a - 1)

let stable_p (a : (int * char * int) array) n =
  let rec doit i =
    if i = n - 1 then true
    else if (fun (xi, _, xd) (yi, _, yd) -> xd = yd && xi > yi) a.(i) a.(i+1) then false
    else doit (i + 1)
  in doit 0

let split str delim =
  let rec doit s acc =
    match
      try Some (String.rindex s delim) with _ -> None
    with
    | None -> s :: acc
    | Some i ->
        let s1 = String.sub s 0 i in
        doit s1 (String.sub s (i + 1) (String.length s - String.length s1 - 1) :: acc)
  in doit str []

let () =
  let n = read_int () in
  let a = Array.init n (fun i ->
    match split (read_line ()) ' ' with
    | [c; d] -> (i, c.[0], int_of_string d)
    | _ -> exit 1
  ) in
  quick_sort a (fun (_, _, x) (_, _, y) -> compare x y);
  print_endline (if stable_p a n then "Stable" else "Not stable");
  Array.iter (fun (_, c, d) -> Printf.printf "%c %d\n" c d) a

Measured memory_bytes: 8868
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<cstring>
#include<cctype>
#include<complex>
#include<iostream>
#include<sstream>
#include<algorithm>
#include<functional>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<bitset>
using namespace std;
const int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};
#define INF 1e+8
#define EPS 1e-8
#define rep(i,j) for(int i = 0; i < (j); i++)
#define reps(i,j,k) for(int i = (j); i < (k); i++)
int main(){
	int h,w;
	while(scanf("%d%d",&w,&h),h){
		int dp[20][20]={{0}};
		int n;
		scanf("%d",&n);
		for(int i = 0; i < n; i++){
			int y,x;
			scanf("%d%d",&x,&y);
			dp[y][x] = -1;
		}
		dp[1][1] = 1;
		for(int i = 1; i <= h; i++){
			for(int j = 1; j <= w; j++){
				if(dp[i][j] == -1)dp[i][j] = 0;
				else dp[i][j] += dp[i-1][j] + dp[i][j-1];
			}
		}
		printf("%d\n",dp[h][w]);
	}
	return 0;
}

Measured memory_bytes: 1188
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
def make_v(*args,e=0):
    from copy import deepcopy
    A=e
    for i in args[::-1]: A=[deepcopy(A) for _ in range(i)]
    return A
input=lambda :sys.stdin.buffer.readline().rstrip()
def resolve():
    n,w=map(int,input().split())
    W=[0]*(n+1)
    V=[0]*(n+1)
    for i in range(n):
        W[i+1],V[i+1]=map(int,input().split())
    dp=make_v(n+1,w+1)
    for i in range(1,n+1):
        for k in range(w+1):
            if(k-W[i]>=0):
                dp[i][k]=max(dp[i-1][k-W[i]]+V[i],dp[i-1][k])
            else:
                dp[i][k]=dp[i-1][k]
    print(dp[n][w])
resolve()

Measured memory_bytes: 145668
import scala.io.StdIn

object Main extends App {
  var continue = true
  var result = new StringBuilder
  while(continue){
    val Array(x, y) = StdIn.readLine().trim.split(' ').map(_.toInt)
    continue = if(x == 0 && y == 0) {
      false
    } else {
      result.append(if(x > y) f"$y $x%n" else f"$x $y%n")
      true
    }
  }
  
  print(result)
}


Measured memory_bytes: 51936
MOD = 10**9 + 7
n, a, b = map(int, input().split())


def pow(x, n, MOD):
    res = 1
    while n:
        if n & 1:
            res *= x
            res %= MOD
        x *= x
        x %= MOD
        n >>= 1
    return res    


def fact(a, b, MOD):
    res = 1
    for i in range(a, b+1):
        res *= i
        res %= MOD
    return res


def combi(n, k, MOD):
    x = fact(n - k + 1, n, MOD)
    y = fact(1, k, MOD)
    return x * pow(y, MOD - 2, MOD) % MOD
    

def solve():
    ans = pow(2, n, MOD) - 1 - combi(n, a, MOD) - combi(n, b, MOD)
    print(ans % MOD)
    #print(pow(2, MOD, MOD))


if __name__ == "__main__":
    solve()

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

int main(){
    string s;
    cin >> s;
    int ans = 700;
    rep(i,3){
        if(s[i] == 'o') ans += 100;
    }
    cout << ans << endl;

}



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

#define pb push_back
#define mp make_pair
#define fs first
#define se second
#define pi 2*acos(0)
#define PI 3.14159265358979323846264338

typedef long long ll;
typedef pair < int , int > pii;
typedef pair < ll , ll > pll;
const int N = 100010;

inline int in() {int x; scanf("%d",&x); return x;}
inline ll lin() {ll x; scanf("%lld",&x); return x;}

int fx[]={1,-1,0,0};
int fy[]={0,0,-1,1};

ll P(ll a, ll b, ll c){
    ll x = min(a, min(b,c));
    ll y = max(a, max(b,c));
    return (y - x);
}

ll Solve(ll h, ll w){
    ll ret = 1ll * 1e18, a, b, c;
    for(ll i = 1ll; i < h; i++){
        a = i * w;
        if(h - i > 1){
            b = (h - i) / 2;
            c = (h - i) / 2;
            if((h - i) % 2ll == 1){
                c++;
            }
            b *= w; c *= w;
            //cout << a << " " << b << " " << c << '\n';
            ret = min(ret, P(a,b,c));
        }
        b = w / 2; c = w / 2;
        if(w % 2 == 1) b++;
        b *= (h - i); c *= (h - i);
        //cout << a << " " << b << " " << c << '\n';
        ret = min(ret, P(a,b,c));
    }
    return ret;
}

int main(){
    ll h = lin(), w = lin();
    printf("%lld\n", min(Solve(h,w), Solve(w,h)));
}


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

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define RFOR(i,b,a) for(int i = (b)-1; i >= (a); --i)
#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a))

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;

const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL)INF;

const int MAX = 100100;
const int MIN = 200;

int RES[MIN][MIN];
int A[MAX];

int main()
{
	//freopen("in.txt", "r", stdin);
	//ios::sync_with_stdio(false); cin.tie(0);

	int h, w;
	scanf("%d%d", &h, &w);
	int n;
	scanf("%d", &n);
	int cnt = 0;
	FOR (i, 0, n)
	{
		int x;
		scanf("%d", &x);
		FOR (j, 0, x)
		{
			A[cnt++] = i + 1;
		}
	}

	int x = 0;
	int y = 0;
	int dir = 1;

	FOR (it, 0, h * w)
	{
		RES[x][y] = A[it];
		y += dir;

		if (y < 0 || y >= w)
		{
			y -= dir;
			x++;
			dir *= -1;
		}
	}

	FOR (i, 0, h)
	{
		FOR (j, 0, w)
		{
			printf("%d ", RES[i][j]);
		}
		printf("\n");
	}

} 


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

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

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

        if(N%1000) cout << 1000-(N%1000)   << endl;
        else cout << 0 << endl;
}

Measured memory_bytes: 3628
n = int(input())
a = reversed(list(map(int, input().split())))
ans = [-1] * n
i = 0
for _a in a:
    if i % 2 == 0:
        ans[i // 2] = _a
    else:
        ans[-((i // 2) + 1)] = _a
    i += 1
for _ans in ans:
    print(_ans, end=" ")


Measured memory_bytes: 94316
#include <iostream>
#include <array>

using std::array;

int main() {
    int n;
    std::cin >> n;
    array<int, 2> cnt{};
    for (int i = 0; i < n; ++i) {
        int a;
        std::cin >> a;
        ++cnt[a % 2];
    }

    if (cnt[0] == 0 || cnt[1] == 0) {
        std::cout << 0 << std::endl;
    } else {
        std::cout << n - (2 - cnt[1] % 2) << std::endl;
    }
    return 0;
}



Measured memory_bytes: 3080