akhauriyash/Code-Regression huggingface dataset:
#include <numeric>
#include <iostream>
#include <sstream>
#include <vector>
#include <cstdio>
#include <map>
#include <set>
#include <functional>
#include <queue>
#include <string>
#include <bitset>
#include <cassert>
#include <algorithm>
#include <cmath>
#include <set>
#include <algorithm>
#include <tuple>
#include <sstream>

using namespace std;

#ifdef LOCAL
#define logv(a) {cerr << #a << " = "; for (auto& e : a) {cerr << e << " ";} cerr << "\n";}
#define logvp(a) {cerr << #a << " = "; for (auto& e : a) {cerr << "(" << e.first << ", " << e.second << ") ";} cerr << "\n";}
#define logvv(a) {cerr << #a << " = \n"; for (auto& r : a) { for (auto& e : r) {cerr << e << " ";} cerr << "\n";} }
#define logvf(a, field) {cerr << #a"."#field << " = \n"; for (auto& e : a) { cerr << e.field << " ";} cerr << "\n"; }
#define logs(a) cerr << #a << " = " << (a) << "\n";
#define logss(a, b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << "\n";
#define logp(a) cerr << #a << " = " << "(" << a.first << ", " << a.second << ")" << "\n";
#define cond(pred, stmt) if (pred) { stmt }
#else
#define logv(a)
#define logvp(a)
#define logvv(a)
#define logvf(a, field)
#define logs(a)
#define logss(a, b)
#define logp(a)
#define cond(pred, stmt)
#endif

#define forn(a, e) for (int a = 0; a < (int)e; a++)
#define forr(a, s, e) for (int a = s; a < (int)e; a++)

using i64 = long long;

template<typename T>
using Pair = array<T, 2>;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    i64 n;
    while (cin >> n) {
        vector<int> p(n);
        forn(i, n) {
            cin >> p[i];
        }
        vector<int> np(n, n), pp(n, -1);
        vector<int> nnp(n, n), ppp(n, -1);
        forn(i, n) {
            int cur = i - 1;
            while (cur != -1 && p[cur] <= p[i]) {
                cur = pp[cur];
            }
            pp[i] = cur;
            if (cur == -1) {
                ppp[i] = -1;
                continue;
            }
            cur--;
            while (cur != -1 && p[cur] <= p[i]) {
                cur = pp[cur];
            }
            ppp[i] = cur;
        }
        for (int i = n - 1; i >= 0; i--) {
            int cur = i + 1;
            while (cur != n && p[cur] <= p[i]) {
                cur = np[cur];
            }
            np[i] = cur;
            if (cur == n) {
                nnp[i] = n;
                continue;
            }
            cur++;
            while (cur != n && p[cur] <= p[i]) {
                cur = np[cur];
            }
            nnp[i] = cur;
        }

        logv(np);
        logv(nnp);
        logv(pp);
        logv(ppp);

        i64 ans = 0;
        forn(i, n) {
            i64 cr = (i - pp[i]) * (nnp[i] - np[i]);
            i64 cl = (np[i] - i) * (pp[i] - ppp[i]);
            ans += p[i] * (cr + cl);
        }
        cout << ans << endl;
    }
}


Measured memory_bytes: 2176
#include<stdio.h>
int main()
{
	long long int n,m,x,y;
	scanf("%lld%lld",&n,&m);
	if(m/2<=n)printf("%lld",m/2);
	else if(m/2>n)
	{
		x=m-n*2;
		y=x/4;
		printf("%lld",y+n);
	}
	return 0;
}

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

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

typedef long long ll;
using namespace std;
int mod = 1000000007;

int main(void){
    int N, Q; cin >> N >> Q;
    string S; cin >> S;
    pair<char, char> cmd[Q];
    rep(i, Q){
        char a, b; cin >> a >> b;
        cmd[i] = make_pair(a, b);
    }
    int ng_left, ok_left, ng_right, ok_right;
    ng_left = -1; ok_left = N;
    ng_right = N; ok_right = -1;

    int m = (ng_left+ok_left)/2;
    while(abs(ng_left-ok_left) > 1){
        bool res = true;
        int pos = m;
        rep(i, Q){
            if(cmd[i].first == S[pos]){
                if(cmd[i].second == 'L') pos--;
                else pos++;
                if(pos < 0) res = false;
            }
        }
        if(res) ok_left = m;
        else ng_left = m;
        m = (ng_left+ok_left)/2;
    }

    m = (ng_right+ok_right)/2;
    while(abs(ng_right-ok_right) > 1){
        bool res = true;
        int pos = m;
        rep(i, Q){
            if(cmd[i].first == S[pos]){
                if(cmd[i].second == 'L') pos--;
                else pos++;
                if(pos >= N) res = false;
            }
        }
        if(res) ok_right = m;
        else ng_right = m;
        m = (ng_right+ok_right)/2;
    }

    cout << max(0, ok_right - ng_left) << endl;
    return 0;
}

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

long long int N, A[202020], b, S;
int main(){
    scanf("%lld", &N);
    for(int i = 0; i < N; ++i){
        scanf("%lld", A + i);
        A[i] -= i - 1;
    }
    sort(A, A + N);
    b = A[N / 2];
    for(int i = 0; i < N; ++i){
        S += abs(A[i] - b);
    }
    cout << S << endl;
    return 0;
}

Measured memory_bytes: 1792
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>

int main(void){

    int N, M;

    scanf("%d%d", &N, &M);

    int g[N+1];
    int f[N+1];

    for(int i = 2; i <= N-1; i++){
        g[i] = 0;
        f[i] = 0;
    }

    int a[M], b[M];

    for(int i = 0; i < M; i++){
        scanf("%d%d", &a[i], &b[i]);
        if(a[i] == 1){
            g[b[i]] = 1;
        }
        if(b[i] == N){
            f[a[i]] = 1;
        }
    }

    int t = 0;

    for(int i = 2; i <= N-1; i++){
        if(g[i] == 1 && f[i] == 1){
            t = 1;
            break;
        }
    }

    if(t == 1){
        printf("POSSIBLE\n");
    }else{
        printf("IMPOSSIBLE\n");
    }

    return 0;
}

Measured memory_bytes: 4728
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n,k; cin>>n>>k;
    if(k>(n-1)*(n-2)/2) {cout<<-1<<endl; return 0;}
    //ウニを作る
    vector <pair<int,int>> graph;
    for(int i=1;i<n;i++){
        graph.push_back({i,n});
    }
    //追加する辺を作る
    vector <pair<int,int>> edge;
    int add = ((n-1)*(n-2)/2 ) - k;
    bool stop = false;
    for(int i=1;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(add == 0) stop = true;
            if(stop) break;
            edge.push_back({i,j});
            add--;
        }
        if(stop) break;
    }
    cout<<edge.size()+graph.size()<<endl;
    for(int i=0;i<graph.size();i++){
        cout<<graph[i].first<<' '<<graph[i].second<<endl;
    }
    for(int i=0;i<edge.size();i++){
        cout<<edge[i].first<<' '<<edge[i].second<<endl;
    }
}


Measured memory_bytes: 384
// AtCoder Regular Contest 016
// C - +/- Rectangle

#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;


int HW[2], hw[2];

int main() {

    int d, k;
    int ij[2];

    cin >> HW[0] >> HW[1] >> hw[0] >> hw[1];

    if (HW[0] % hw[0] != 0) {
        d = 0;
    } else if (HW[1] % hw[1] != 0) {
        d = 1;
    } else {
        cout << "No" << endl;
        return 0;
    }

    cout << "Yes" << endl;
    k = HW[d] / hw[d] + 1;
    for (ij[0] = 0; ij[0] < HW[0]; ij[0]++) {
        for (ij[1] = 0; ij[1] < HW[1]; ij[1]++) {
            if (ij[d] % hw[d] == 0) {
                cout << k;
            } else if(ij[d] % hw[d] == hw[d] - 1) {
                cout << -k - 1;
            } else {
                cout << 0;
            }
            cout << (ij[1] == HW[1] - 1 ? '\n' : ' ');
        }
    }

    return 0;

}





Measured memory_bytes: 1280
#include <iostream>
#include <map>
#include <algorithm>
#include <string>
#include <vector> 
#include <numeric>
#include <cmath>


#define CHMAX(a,b) a = std::max(a,b)
#define CHMIN(a,b) a = std::min(a,b)
#define CHABS(a) a = std::abs(a) 
#define COUT(a) std::cout << a << std::endl
#define CERR(a) std::cerr << a << std::endl

using namespace std;
using lli = long long int;

lli mod197 = 1000000007LL;

// ax + by = gcd(a,b) 最大公約数
template< typename T >
T extgcd(T a, T b, T& x, T& y) {
	T d = a;
	if (b != 0) {
		d = extgcd(b, a % b, y, x);
		y -= (a / b) * x;
	}
	else {
		x = 1;
		y = 0;
	}
	return d;
}

lli X[100000] = {};
lli section[100000] = {};

int main(void) {

	lli N, M;

	cin >> N >> M;

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

	sort(X, X + M);

	for (int i = 0; i < M - 1; i++) {
		section[i] = X[i + 1] - X[i];
	}

	sort(section, section + M - 1);

	lli ans = 0;

	for (int i = 0; i < M - N; i++) {
		ans += section[i];
	}

	COUT(ans);

	return 0;
}

Measured memory_bytes: 1792
import java.util.Set;
import java.util.HashSet;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < N; i++) {
            int A = sc.nextInt();
            if (set.contains(A)) {
                set.remove(A);
            } else {
                set.add(A);
            }
        }
        System.out.println(set.size());
        sc.close();
    }
}

Measured memory_bytes: 61212
s=input()
t=input()
sz=len(t)
ans=100000000000
c=0
if len(s)==sz:
    c=0
    for j in range(sz):
        if s[j]==t[j]:
            c+=1
        else:
            ans=min(ans,sz-c)
else:
    for i in range(0,len(s)-sz):
        k=s[i:i+sz]
        c=0
        for j in range(sz):
            if k[j]==t[j]:
                c+=1
            else:
                ans=min(ans,sz-c)
        # print(c)
ans=min(ans,sz-c)
print(ans)


Measured memory_bytes: 8896
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#define inf 1<<30
using namespace std;
char s[3];
int main(){
	scanf("%s",s);
	for(int i=0;i<3;i++){
		if(s[i]=='1')s[i]='9';
		else if(s[i]=='9')s[i]='1';
	}
	printf("%s",s);
	return 0;
}

Measured memory_bytes: 256
// luogu-judger-enable-o2
#include<stdio.h>
int main()
{
	int x,i,sum=0;
	scanf("%d",&x);
	if(x<0) x=-x;
	for(i=0;sum<x;i++)
		sum+=i;
	printf("%d",i-1);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define SIZE 200005
#define INF 1000000005LL
#define MOD 1000000007

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

int N,M,Q;
int A[505][505];

int main()
{
	cin >> N >> M >> Q;
	int l,r;
	rep(i,0,M){
		cin >> l >> r;
		l--;r--;
		A[0][r]++;
		A[0][N]--;
		A[l+1][r]--;
		A[l+1][N]++;
	}
	rep(i,0,N) rep(j,0,N) A[i][j+1] += A[i][j];
	rep(j,0,N) rep(i,0,N) A[i+1][j] += A[i][j];

	rep(i,0,Q){
		cin >> l >> r;
		l--;r--;
		cout << A[l][r] << endl;
	}


	return 0;
}


Measured memory_bytes: 1920
t1, t2 = map(int, input().split())
a1, a2 = map(int, input().split())
b1, b2 = map(int, input().split())

ave_a = t1 * a1 + t2 * a2
ave_b = t1 * b1 + t2 * b2
if ave_a < ave_b:
    (a1, a2), (b1, b2) = (b1, b2), (a1, a2)
    ave_a, ave_b = ave_b, ave_a

if ave_a == ave_b:
    print('infinity')
    exit()

half, all = t1 * (b1 - a1), ave_a - ave_b
ans = half // all * 2 + (half % all != 0)
print(max(0, ans))


Measured memory_bytes: 61856
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int N;
	int ans = 1;
	long long S = 0;

	cin >> N;

	vector<int> A(N);

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

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

	for (int i = 0;i < N - 1;i++)
	{
		S += A[i];
		if (S * 2 >= A[i + 1])
			ans++;
		else
			ans = 1;
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using vb = vector<bool>;
#define FOR(i,a,b) for(ll i = (a); i < (b); i++)

int main() {
    ll k; cin >> k;

    ll num = 0;
    FOR(i, 1, 1000008) {
        num = num*10 + 7;

        num %= k;
        if(num == 0) {
            cout << i << endl;
            return 0;
        }
    }

    cout << -1 << endl;
}

Measured memory_bytes: 3568
#include<bits/stdc++.h>
using namespace std;
#define N 100010
#define ll long long
int a[1010];
int main()
{
    int n,m;
    cin>>n>>m;
    while(m--){
        int x,y;
        cin>>x;
        for(int i = 0; i < x; i++){
            cin>>y;
            a[y]++;
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++){
        if(a[i] == 0){
            ans++;
        }
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 3620
Scanf.scanf "%d %d %d %d" (fun sx sy tx ty ->
    for i = sx to tx - 1 do print_char 'R' done;
    for i = sy to ty - 1 do print_char 'U' done;
    for i = sx to tx - 1 do print_char 'L' done;
    for i = sy to ty - 1 do print_char 'D' done;
    print_char 'D';
    for i = sx to tx     do print_char 'R' done;
    print_char 'U';
    for i = sy to ty - 1 do print_char 'U' done;
    print_char 'L';
    print_char 'U';
    for i = sx to tx     do print_char 'L' done;
    print_char 'D';
    for i = sy to ty - 1 do print_char 'D' done;
    print_char 'R';
    print_newline ()
)

Measured memory_bytes: 3692
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n-1;i>=a;i--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define pb push_back


///Input/Output macros!
#define gi(x) scanf("%d", &x)
#define gi2(x, y) scanf("%d%d", &x, &y)
#define gi3(x, y, z) scanf("%d%d%d", &x, &y, &z)
#define gill(x) scanf("%lld", &x)
#define gill2(x, y) scanf("%lld%lld", &x, &y)
#define gill3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z)
#define pi(x) printf("%d\n", x)
#define pill(x) printf("%lld\n", x)


///Basic Debugging macros!
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(ll __i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(ll __i__=0;__i__<r;__i__++){for(ll __j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}

using namespace std;

///Power of 2 till 2^31!
ll pow2[32] = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824,2147483648};

///Power function!
ll power(ll x,ll y)
{
        ll res = 1;
        while(y>0){
            if(y&1)
                res *= x;
            y>>=1;
            x*=x;
        }
        return res;
}

///Basic Sieve of Eratosthenes!
void Sieve(ll n)
{
    bool prime[n+1];
    memset(prime, true, sizeof(prime));
    for (ll p=2; p*p<=n; p++)
    {
        if (prime[p] == true)
        {
            for (ll i=p*p; i<=n; i += p)
                prime[i] = false;
        }
    }
    for (ll p=2; p<=n; p++)
       if (prime[p])
          cout << p << " ";
}

ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

bool isPerfectSquare(ll x){ ll s = sqrt(x); return (s*s == x);}

bool isFibonacci(int n){return isPerfectSquare(5*n*n + 4) || isPerfectSquare(5*n*n - 4);}

bool isPrime(int n){if (n <= 1)return false;if (n <= 3)  return true;
    if (n%2 == 0 || n%3 == 0) return false;
    for (int i=5; i*i<=n; i=i+6) if (n%i == 0 || n%(i+2) == 0)return false;
    return true;
}

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;


const int MOD = 1000000007;
const long double PI = 4*atan((long double)1);
const ll INF = 1e18;

int main()
{
    ios::sync_with_stdio(false);
    int a,b,c;
    cin>>a>>b>>c;
    if(a+b+c >= 22){
        cout<<"bust"<<'\n';
    }
    else{
        cout<<"win"<<'\n';
    }
}


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

long long int K, S, i, a;

int main(){
    scanf("%lld%lld", &K, &S);
    for(i = 0; i <= K; ++i){
        a += max(0LL, (S - i < K)?S - i + 1:K * 2 - S + i + 1);
    }
    cout << a << endl;
    return 0;
}


Measured memory_bytes: 256
import re
from collections import defaultdict
n = int(input())
ss = [input() for i in range(n)]

cnt = 0
for s in ss:
  cnt += len(re.findall(r'AB', s))

#print(cnt)

headtail = defaultdict(int)
for s in ss:
  if re.search('^B', s) and re.search('A$', s):
    headtail['ba'] += 1
  elif re.search('^B', s):
    headtail['b'] += 1
  elif re.search('A$', s):
    headtail['a'] += 1
#print(headtail)

cnt_connect = 0

if headtail['ba'] > 0:
  cnt_connect = headtail['ba'] - 1
  if headtail['a'] > 0:
    headtail['a'] -= 1
    cnt_connect += 1
  if headtail['b'] > 0:
    headtail['b'] -= 1
    cnt_connect += 1
cnt_connect += min([headtail['a'], headtail['b']])
#print(headtail)
#print(cnt_connect)

cnt = cnt + cnt_connect

print(cnt)


Measured memory_bytes: 4212
#include <bits/stdc++.h>
using namespace std;
#define ll long long
static const ll MAX=100010*2;
static const ll INF=1000000000000000000;
ll N;
ll a[MAX],sum[MAX];

void solve(){
	cin >>N;
	a[0]=sum[0]=0;
	for(int i=1;i<=N;i++){
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
	}
	ll ans=INF;
	for(int k=1;k<=N-1;++k){
		ll x=sum[k]-sum[0];
		ll y=sum[N]-sum[k];
		ans=min(ans,abs(x-y));
	}
	cout<<ans<<endl;
}
int main() {
	solve();

	return 0;
}


Measured memory_bytes: 3328
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include<set>
#include<map>
using namespace std;


int main() {
    int a, b;
    cin >> a >> b;
    if(a < 10){
        cout << b + 100*(10-a);
    }
    else
    {
        cout << b;
    }
    
    
    
    cout << endl;
}


Measured memory_bytes: 256
from decimal import *
from math import *
a, b, h, m = map(float, input().split())
ana = 360*(60*h+m)/720
anb = 360*m/60
an = min(abs(ana-anb), abs(anb-ana))
sint = sin(radians(an))
cost = cos(radians(an))
l = Decimal(((b-a*cost)**2 + (a*sint)**2)**.5)
print(l)

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

typedef uint64_t u64;
typedef int64_t i64;
typedef uint32_t u32;
typedef int32_t i32;

#define MAX_NUM (1000000007)
#define PI 3.14159265358979323846

using namespace std;

template <typename T>
static inline void ArrayInput(vector<T>& A) {
  for (auto itr = A.begin(); itr < A.end(); ++itr) cin >> *itr;
}

template <typename T>
static inline void ArrayPut(const vector<T>& A) {
  for (auto itr = A.begin(); itr < A.end(); ++itr) cout << *itr << " ";
  cout << endl;
}

template <typename T>
static inline T ArraySum(vector<T>& A) {
  T res = 0;
  for (auto itr = A.begin(); itr < A.end(); ++itr) res += *itr;
  return res;
}

bool Sec_compare(pair<uint64_t, uint64_t> a, pair<uint64_t, uint64_t> b) {
  if (a.second != b.second) {
    return a.second < b.second;
  } else {
    return a.first > b.first;
  }
}

u64 dec_dig(u64 num) {
  u64 res = 0;
  while (num > 0) {
    num /= 10;
    ++res;
  }
  return res;
}

i64 modinv(i64 a, i64 m) {
  i64 b = m, u = 1, v = 0;
  while (b) {
    i64 t = a / b;
    a -= t * b;
    swap(a, b);
    u -= t * v;
    swap(u, v);
  }
  u %= m;
  if (u < 0) u += m;
  return u;
}

u64 gcd(u64 a, u64 b) {
  if (a < b) {
    a ^= b;
    b ^= a;
    a ^= b;
  }

  return b ? gcd(b, a % b) : a;
}

i64 My_Comb(u64 n, u64 k, i64 m) {
  if (n < k) return 0;
  if (k == 0 || n == k) return 1;
  u64 res = 1;
  k = (n / 2 < k) ? n - k : k;
  for (u64 i = 1; i <= k; ++i)
    res = (((res * (n + 1 - i)) % m) * modinv(i, m)) % m;
  return res;
}

i64 My_Pow(u64 a, u64 n, i64 m) {
  u64 tmp = n, calc = 1;
  while (tmp > 0) {
    if (tmp % 2) {
      tmp--;
      calc *= a;
      calc %= m;
    } else {
      a *= a;
      a %= m;
      tmp /= 2;
    }
  }
  return calc;
}

class UnionFind {
 public:
  vector<u64> Par;
  vector<u64> sz;

  UnionFind(u64 n);
  u64 root(u64 x);
  bool same(u64 x, u64 y);
  void unite(u64 x, u64 y);
  u64 size(u64 x);
};

UnionFind::UnionFind(u64 n) {
  Par.resize(n);
  sz.assign(n, 1);
  for (u64 i = 0; i < n; ++i) Par[i] = i;
}

u64 UnionFind::root(u64 x) {
  if (Par[x] == x) {
    return x;
  } else {
    return Par[x] = root(Par[x]);
  }
}

bool UnionFind::same(u64 x, u64 y) { return root(x) == root(y); }

u64 UnionFind::size(u64 x) { return sz[root(x)]; }

void UnionFind::unite(u64 x, u64 y) {
  x = root(x);
  y = root(y);
  if (x == y) return;
  if (sz[x] < sz[y]) swap(x, y);
  sz[x] += sz[y];
  Par[y] = x;
}

template <typename T>
i64 BinSearch(vector<T>& V, i64 comp) {
  i64 l = 0, r = V.size() - 1;
  if (V[l] > V[r]) swap(l, r);
  if (V[l] >= comp) return l;
  if (V[r] <= comp) return r;
  while (abs(r - l) > 1) {
    i64 index = (l + r) / 2;
    if (V[index] == comp)
      return index;
    else if (V[index] > comp)
      r = index;
    else
      l = index;
  }
  if (abs(V[l] - comp) < abs(V[r] - comp))
    return l;
  else
    return r;
}

int main() {
  cout << setprecision(18);
  string S;
  cin >> S;
  for (u32 i = 0; i < 3; ++i) {
    cout << S[i];
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 3600
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
inline void rd(int &x){
  int k, m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(int x){
  char f[10];
  int m=0, s=0;
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
int N;
int K;
int L[50];
int main(){
  int i, res=0;
  rd(N);
  rd(K);
  {
    int Lj4PdHRW;
    for(Lj4PdHRW=0;Lj4PdHRW<(N);Lj4PdHRW++){
      rd(L[Lj4PdHRW]);
    }
  }
  sort(L, L+N);
  for(i=0;i<(K);i++){
    res += L[N-K+i];
  }
  wt_L(res);
  wt_L('\n');
  return 0;
}
// cLay varsion 20190822-2

// --- original code ---
// int N, K, L[50];
// {
//   int i, res = 0;
//   rd(N, K, L(N));
//   sort(L, L+N);
//   rep(i,K) res += L[N-K+i];
//   wt(res);
// }


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

using namespace std;

int solve(int g, vector<pair<int, int>>& scores, vector<int>& complete,
          vector<bool> used, int current) {
    int size = scores.size();
    if (current >= size) {
        int count = 0;
        int score = 0;
        for (int i = 0; i < size; ++i) {
            if (used[i]) {
                count += scores[i].first;
                score += complete[i];
            }
        }

        if (score >= g) {
            return count;
        } else {
            bool flag = false;
            for (int i = size - 1; i >= 0; --i) {
                if (used[i])
                    continue;

                for (int j = 0; j < scores[i].first; ++j) {
                    score += (i + 1) * 100;
                    ++count;
                    if (score >= g) {
                        flag = true;
                        break;
                    }
                }
                if (flag)
                    break;
                score += scores[i].second;
            }
            return count;
        }
    } else {
        int res = solve(g, scores, complete, used, current + 1);
        used[current] = true;
        res = min(res, solve(g, scores, complete, used, current + 1));
        return res;
    }
}

int main() {
    int d, g;
    cin >> d >> g;

    vector<pair<int, int>> scores(d);
    for (int i = 0; i < d; ++i) {
        int p, c;
        cin >> p >> c;
        scores[i] = make_pair(p, c);
    }

    vector<int> complete(d);
    for (int i = 0; i < d; ++i)
        complete[i] = (i + 1) * 100 * scores[i].first + scores[i].second;

    vector<bool> used(d, false);
    int count = solve(g, scores, complete, used, 0);
    cout << count << '\n';
}


Measured memory_bytes: 256
#include <cmath>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
using namespace std;
#define REP(i,n) for(int i = 0; i < n; i++)

int main(void)
{
    int N;
    cin >> N;
    string S[N];
    map<string , int> mp;

    for(int i = 0; i < N; i++)
        cin >> S[i];
    
    for(int i = 0; i < N; i++){
        mp[S[i]]++;
    }

    if(mp.size() == 3)
        cout << "Three" << endl;
    else if(mp.size() == 4)
        cout << "Four" << endl;


    return 0;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr long long INFL = numeric_limits<long long>::max() / 2;
constexpr int MOD = 1000000007;


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

    int N;
    cin >> N;

    pair<pair<string,int>,int> p[N];
    rep(i,N){
        string s;
        int x;
        cin >> s >> x;
        p[i]={{s,-x},i+1};
    }
    sort(p,p+N);
    rep(i,N){
        cout << p[i].second << endl;
    }


}


Measured memory_bytes: 256
import sys

def main():

	A,B,C,D = map(int, input().split())
	
	while A > 0 and C > 0:
		
		C = C - B
		if C <= 0:
			print("Yes")
			break
		
		A = A - D
		if A <= 0:
			print("No")

if __name__ == "__main__":
    main()

Measured memory_bytes: 9176
# -*- coding: utf-8 -*-
import math


def main():
    bingo_card_number = [list(map(int, input().split())) for i in range(3)]
    n = int(input())
    number_called = [int(input()) for i in range(n)]

    bingo_card = [[0] * 3 for _ in range(3)]

    for i, row in enumerate(bingo_card_number):
        for j, cell in enumerate(row):
            if cell in number_called:
                bingo_card[i][j] = 1

    result = "No"
    for i in range(3):

        if sum(bingo_card[i]) == 3:
            result = "Yes"

        if bingo_card[0][i] + bingo_card[1][i] + bingo_card[2][i] == 3:
            result = "Yes"

    if bingo_card[0][0] + bingo_card[1][1] + bingo_card[2][2] == 3\
        or bingo_card[2][0] + bingo_card[1][1] + bingo_card[0][2] == 3:
        result = "Yes"


    print(result)


if __name__ == '__main__':
    main()


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

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define start_routine() int begtime = clock();
#define end_routine() int endtime = clock(); cerr << endl << "Time elapsed: " << (endtime - begtime)*1000/CLOCKS_PER_SEC << " ms"; return 0
#define speed() cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(false)
// #define exit(a, b) return cout << a, b;

#define PB push_back
#define MP make_pair

#define sd(n) scanf("%lld", &n)
#define pdn(n) printf("%lld\n", n);
#define pds(n) printf("%lld ", n);
#define endl '\n'

#define forn(a, b, i) for (int i = a; i < b; i += 1)
#define all(v) v.begin(), v.end() 

#define print(stuff) cout << stuff << endl
#define len(stuff) (int) stuff.size()

#define int long long
// #define float long double 
#define ll long long
#define ld long double

typedef long long LL;

using vi = vector<int>;
using vb = vector<bool>;
using pii = pair<int, int>;
using mii = map<int, int>;

const int inf = (int) 1e16;
const int upper = (int) 3e5 + 50;
// const int M = (ll) 1e9 + 7;
const int mod = (ll) 998244353;
const int M = mod;

const double eps =  1e-8;
	
int n, k;

int modexp (int a, int b) {
	if (b == 0) return 1;
	int ans = modexp(a, b/2);
	ans = (ans * ans) % mod;
	if (b & 1) ans = (ans * a) % mod;
	return ans;
}

int inv (int a) {
	return modexp(a, mod - 2);
}

int fac[2000005], invfac[2000005];
void compute() {
	fac[0] = 1;
	for (int i = 1; i <= 2000000; i += 1) {
		fac[i] = (fac[i - 1] * i) % mod;
	}
	invfac[2000000] = inv(fac[2000000]);
	for (int i = 2000000 - 1; i >= 0; i--) {
		invfac[i] = (invfac[i + 1] * (i + 1)) % mod;
	}
}

inline int c (int a, int b) {
	if (b > a) return 0;
	int ans = fac[a];
	ans *= invfac[a - b], ans %= mod;
	ans *= invfac[b], ans %= mod;
	return ans;
}

int arr[upper];
int p[upper], pos[upper];
int sz[upper];

void make_set (int v) {
	sz[v] = 1;
	p[v] = v;
}

int find_set (int v) {
	if (p[v] == v) return v;
	else return p[v] = find_set(p[v]);
}

void merge_set (int a, int b) {
	a = find_set(a), b = find_set(b);
	if (a == b) return;
	if (sz[a] < sz[b]) swap(a, b);
	p[b] = a;
	sz[a] += sz[b];
}

signed main () {
	start_routine();
	speed();
	#ifndef ONLINE_JUDGE
	// freopen("input.txt", "r", stdin);	 
	// freopen("output.txt", "w", stdout);
	// freopen("errlog.txt", "w", stderr);
	#endif		
	memset(sz, 0, sizeof sz);
	memset(p, 0, sizeof p);

	int n; cin >> n;
	for (int i = 0; i <= n + 1; i += 1) {
		arr[i] = 0;
	}
	for (int i = 1; i <= n; i += 1) 
		cin >> arr[i], pos[arr[i]] = i;
	for (int i = 1; i <= n; i += 1) {
		make_set(i);
	}
	int ans = 0;
	for (int i = n; i >= 1; i -= 1) {
		int position = pos[i];
		int nxt = arr[position + 1];
		int prv = arr[position - 1];

		int eligible_l = 1, eligible_r = 1;
		if (prv > i) eligible_l = sz[find_set(prv)] + 1;
		if (nxt > i) eligible_r = sz[find_set(nxt)] + 1;
		ans += (i * eligible_l * eligible_r);

		if (nxt > i) merge_set(i, nxt);
		if (prv > i) merge_set(i, prv);
	} 
	cout << ans;
 	end_routine();		
}


Measured memory_bytes: 10496
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int compar(const int *val1, const int *val2);
int poker(int *ary);

int main(void) {
	int ary[5];
	int n;
	int i,m;
	char str[100],*line;

	for( ;fgets(str,sizeof(str),stdin)!=NULL; ){
	line=strtok(str,", ");
	sscanf(line,"%d",&m);
	ary[0]=m;
	for(i=1;i<5;i++){
		line=strtok(NULL,", ");
		sscanf(line,"%d",&m);
		ary[i]=m;
	}
	n = sizeof(ary)/sizeof(ary[0]);
	qsort(ary, n, sizeof(int),(int (*)(const void *, const void *))compar);
	poker(ary);
	}
	return 0;
}

int compar(const int *val1, const int *val2) {
    if ( *val1 < *val2 ) {
        return -1;
    } else if ( *val1 == * val2 ) {
        return 0;
    } else {
        return 1;
    }
}

int poker(int *ary){
	if((ary[0]==ary[1] && ary[1]==ary[2] && ary[2]==ary[3]) || (ary[1]==ary[2] && ary[2]==ary[3] && ary[3]==ary[4]))
		printf("four card\n");
	else if((ary[0]==ary[1] && ary[1]==ary[2]) && (ary[3]==ary[4]) || (ary[2]==ary[3] && ary[3]==ary[4]) && (ary[0]==ary[1]))
		printf("full house\n");
	else if((ary[0]==ary[1]-1 && ary[1]==ary[2]-1) && (ary[2]==ary[3]-1) && (ary[3]==ary[4]-1))
		printf("straight\n");
	else if((ary[0]==ary[1]-9 && ary[1]==ary[2]-1) && (ary[2]==ary[3]-1) && (ary[3]==ary[4]-1))
		printf("straight\n");
	else if((ary[0]==ary[1] && ary[1]==ary[2]) || (ary[1]==ary[2] && ary[2]==ary[3]) || (ary[2]==ary[3] && ary[3]==ary[4]))
		printf("three card\n");
	else if((ary[0]==ary[1] && ary[2]==ary[3]) || (ary[0]==ary[1] && ary[3]==ary[4]) || (ary[1]==ary[2] && ary[3]==ary[4]))
		printf("two pair\n");
	else if(ary[0]==ary[1] || ary[1]==ary[2] || ary[2]==ary[3] || ary[3]==ary[4])
		printf("one pair\n");
	else
		printf("null\n");
	return 0;
}

Measured memory_bytes: 592
#define _USE_MATH_DEFINES
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<cstring>
#include<stack>
#include<functional>
#include<sstream>
using namespace std;
typedef long long ll;

const double INF = 1e9;

int N;
double dp[1 << 15][15];
int prev_[1 << 15][15];

int main(){
	int num[15], d[15], size[15];
	cin >> N;
	for(int i = 0; i < N; i++)
	{
		cin >> num[i] >> d[i] >> size[i];
	}

	fill_n((double*)dp, (1 << 15) * 15, INF);
	//fill_n((int*)prev_, (1 << 15) * 15, -1);
	for(int i = 0; i < N; i++) dp[0][i] = 0;

	for(int i = 0; i < (1 << N); i++)
	{
		int w = 0;
		for(int j = 0; j < N; j++)
		{
			w += size[j] * 20 * ((i >> j) & 1);
		}
		for(int j = 0; j < N; j++)
		{
			if(dp[i][j] > INF - 1) continue;
			for(int k = 0; k < N; k++)
			{
				if(j == k) continue;
				int nextS = i | (1 << k);
				double nextT = dp[i][j] + abs(d[j] - d[k]) * (70.0 + w) / 2000.0;
				if(dp[nextS][k] > nextT)
				{
					dp[nextS][k] = nextT;
					prev_[nextS][k] = j;
				}
			}
		}
	}

	vector<int> ans;
	int pos, s = (1 << N) - 1;
	double mi = INF;
	for(int i = 0; i < N; i++)
	{
		if(mi > dp[s][i])
		{
			pos = i;
			mi = dp[s][i];
		}
	}

	ans.push_back(pos);
	while(true)
	{
		int nextS = s ^ (1 << pos);
		pos = prev_[s][pos];
		s = nextS;
		if(s == 0) break;
		ans.push_back(pos);
	}

	for(int i = ans.size() - 1; i > 0; i--)
	{
		printf("%d ", num[ans[i]]);
	}
	printf("%d\n", num[ans[0]]);
	return 0;
}

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

using ll = long long int;

const ll MAXN = 3001;
ll S[MAXN][MAXN];
ll dp[MAXN][MAXN][4];

int main()
{
    ll R, C, K;
    cin >> R >> C >> K;

    for (ll i=0;i<K;++i)
    {
        ll x, y;
        cin >> y >> x;
        cin >> S[x][y];
    }

    ll ans = 0;

    const auto update = [&ans](auto* dst, auto src)
    {
        *dst = max(*dst, src);
        ans = max(ans, *dst);
    };

    for (ll y=1;y<=R;++y)
    for (ll x=1;x<=C;++x)
    for (ll k=1;k<=3;++k)
    {
        update(&dp[x][y][k], dp[x - 1][y][k]);
        update(&dp[x][y][k], dp[x - 1][y][k - 1] + S[x][y]);

        update(&dp[x][y][0], dp[x][y - 1][k]);
        update(&dp[x][y][1], dp[x][y - 1][k] + S[x][y]);
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 355156
import java.util.*;


public class Main{
  public static void main(String[] arg){
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    String S = sc.next();
    char I = 'I';
    int ans = 0;
    int maxAns = 0;
    char[]list = S.toCharArray();
    for(int i = 0; i < N; i++){
      // char A = list[i];
      if(list[i] == I){
        ans +=1;
        if(maxAns<ans){
          maxAns = ans;
        }
      }else{
        ans -=1;
      }
    }
    System.out.println(maxAns);
  }
}

Measured memory_bytes: 23764
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
using ll = long long;
using ld = long double;
#define vl vector<long long>
#define vvl vector<vector<long long>>
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
using pll = pair<long long,long long>;
#define cY cout<<"Yes"<<endl
#define cN cout<<"No"<<endl
const long long INF = 1LL << 60;
const long long MOD = 1000000007;
const long double pi = (acos(-1));
#define pb push_back
#define vs vector<string>

//最大最小の入れ替え
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

//約数列挙
vector<long long> divisor(long long n) {
    vector<long long> ret;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i * i != n) ret.push_back(n / i);
        }
    }
    sort(ret.begin(), ret.end()); // 昇順に並べる
    return ret;
}
//コンビネーション
ll nCr(ll n, ll r) {
    ll ans = 1;
    for (ll i = n; i > n - r; --i) {
        ans = ans*i;
    }
    for (ll i = 1 ; i < r + 1; ++i) {
        ans = ans / i;
    }
    return ans;
}
//素因数分解
map< ll, ll > prime_factor(ll n) {
  map< ll, ll > ret;
  for(ll i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1) ret[n] = 1;
  return ret;
}

//切り上げの割り算は(a + b - 1) / bでできる

//ここから
int main(){
    ll N,M;
    cin>>N>>M;
    cout<<abs((N-2)*(M-2))<<endl;
}


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

#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()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int mod = (int)1e9+7;
void dbg(){ cerr << "\n"; }  template <typename T,typename ...T2> void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }
template <class T> void amin(T& a,T b){ a=min(a,b);}
template <class T> void amax(T& a,T b){ a=max(a,b);}

int main()
{
	//cin.tie(0); ios_base::sync_with_stdio(false);
	int a,b, ans=0;

	cin >>a >>b;
	
	if(b%a==0) cout <<a+b <<"\n";
	else cout <<b-a <<"\n";

	return 0;
}



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

#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(a) (a).begin(), (a).end()

using namespace std;

int main() {
    int yyyy, mm, dd;

    scanf("%d/%d/%d", &yyyy, &mm, &dd);
    yyyy++;

    printf("%4d/%02d/%02d\n", yyyy, mm, dd);

    return 0;
}


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

int main(){
    int min=-1,max=0;
    string s;
    cin >> s;
    for(int i=0;i<s.size();i++){
        if(s[i]=='A' && min == -1){
            min = i;
        }

        if(s[i]=='Z'){
            if(max<i){
                max = i;
            }
        }
    }

    cout << max - min +1 << endl; 
}



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

int64_t k(int64_t l){
  int64_t v=1;
  for(int i=0; i<l; i++){
    v= v*2;
    v=v%1000000007;
  }
  return v;
}

int main(){
  int n;
  cin >> n;
  vector<int64_t> a(61);
  vector<int64_t> b(61);
  for(int i=0; i<n; i++){
    int64_t x;
    cin >> x;
    bitset<61> y(x);
    for(int j=0; j<61; j++){
      if(y.test(j)==1) a.at(j)++;
      else b.at(j)++;
    }
  }
  int64_t ans=0;
  for(int i=0; i<61; i++){
    ans += ((a.at(i)*b.at(i))%1000000007)*k(i)%1000000007;
    ans = ans%1000000007;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
def num2alpha(num):
    if num<=26:
        return chr(64+num)
    elif num%26==0:
        return num2alpha(num//26-1)+chr(90)
    else:
        return num2alpha(num//26)+chr(64+num%26)
      
n = int(input())
print(num2alpha(n).lower())

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

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

    unsigned long num = 0;
    unsigned long pre_num = 1;
    unsigned long pre_pre_num = 2;

    if (N == 1) {
        num = 1;
    } else {
        for (int i = 0; i < (N-1); i++) {
            num = pre_num + pre_pre_num;
            pre_pre_num = pre_num;
            pre_num = num;
        }
    }

    cout << num << endl;
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll N,M,i,a,c = 0;scanf("%lld%lld",&N,&M);
  map<ll,ll> mp;
  mp[0] = 1;
  for(i=0;i<N;i++){
    scanf("%lld",&a);
    c = (c+a) % M;
    if(mp.find(c) != mp.end()) mp[c]++;
    else mp[c] = 1;
  }
  ll ans = 0;
  for(auto itr = mp.begin();itr != mp.end();itr++) ans += itr->second*(itr->second-1)/2;
  printf("%lld\n",ans);
}


Measured memory_bytes: 7596
#include <stdio.h>
int main(void)
{
	int n, i, a, min = 1000000, max = -1000000;
	long long z = 0;
	scanf("%d", &n);
	for (i = 1; i <= n; i++)
	{
		scanf("%d", &a);
		min = (min > a) ? a : min;
		max = (max < a) ? a : max;
		z = z + a;
	}
	printf("%d %d %lld\n", min, max, z);
	return 0;
}

Measured memory_bytes: 600
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#define rep(i,n) for(int i = 0; i < n; ++i )
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
  int n;
  cin >> n;
  vector<ll> l(n);
  rep(i,n) cin >> l[i];
  int ans = 0;
  rep(i,n)rep(j,n)rep(k,n){
    if(l[i]==l[j]||l[j]==l[k]||l[k]==l[i]) continue;
    if(i<j&&j<k){
      ll s = l[i]+l[j]+l[k];
      ll m = max({l[i],l[j],l[k]});
      if(m<s-m) ++ans;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 3648
#include <iostream>
//#include <iomanip>
//#include <string>
#include <vector>
//#include <algorithm>
//#include <utility>
//#include <set>
//#include <map>
//#include <queue>
//#include <deque>
//#include <bitset>
//#include <math.h>
using namespace std ;
using ll = long long ;
//using ld = long double ;
using vll = vector<ll> ;
//using vvll = vector<vll> ;
//using vc = vector<char> ;
//using vvc = vector<vc> ;
//using vb = vector<bool> ;
//using vvb = vector<vb> ;
//using pll = pair<ll,ll> ;

ll mod = 1000000007 ;
//long double pie = acos(-1) ;

//string yorn(bool a){if(a) return"Yes" ; return "No" ;}
//string YorN(bool a){if(a) return"YES" ; return "NO" ;}
//ll gcd(long long a,long long b){if(b==0) return a ; return gcd(b,a%b) ;}
//ll lcm(long long a,long long b){return a/gcd(a,b)*b ;}
//ll sa(long long a,long long b){if(a>b) return a-b ; return b-a ;}
//void mysort(vector<long long> &a){sort(a.begin(),a.end()) ;}
//void myrev(vector<long long> &a){reverse(a.begin(),a.end()) ;}

int main(){
	ll n,k ;
	cin >> n >> k ;
	vll a(n) ;
	for(auto &i:a) cin >> i ;
	vll l(n,0),r(n,0) ;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(a.at(i)>a.at(j)){
				if(i>j) l.at(i)++ ;
				else r.at(i)++ ;
			}
		}
	}
	ll ans = 0 ;
	for(int i=0;i<n;i++){
		ll sub = k*(k+1)/2%mod*r.at(i)+k*(k-1)/2%mod*l.at(i) ;
		ans += sub%mod ;
		ans %= mod ;
	}
	cout << ans << endl ;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <cmath>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);i <= (e);(i)++)

#define int long long

int N;
i64 L,T;
vector<i64> X;
vector<i64> W;
vector<i64> Xs;

signed main(){
  cin >> N >> L >> T;
  X.resize(N);
  W.resize(N);
  rep(i,0,N - 1){
    cin >> X[i] >> W[i];
    if(W[i] == 1){
      Xs.push_back((X[i] + T) % L);
    }
    else{
      Xs.push_back((X[i] + L + (-T) % L ) % L);
    }
  }

  i64 zero = Xs.front();

  sort(begin(Xs),end(Xs));

  i64 cou = 0;

  rep(i,1,N - 1){
    if(W[0] != W[i]){
      i64 re = 0;
      if(W[0] == 1){
        re = X[i] - X[0];
      }
      else{
        re = (X[0] + L) - X[i];
      }
      if(re <= T * 2){
        i64 t = T * 2 - re;
        cou++;
        cou += t / (L);
      }
    }
  }


  if(W[0] == 2){
    cou = N + (- cou) % N;
  }

  vector<int> ans(N);
  int from = lower_bound(begin(Xs),end(Xs),zero) - begin(Xs);
  if(W[0] == 1 && Xs[from] == Xs[(from + 1) % N]){
    from++;
  }

  rep(i,0,N - 1){
    int index = (from + i) % N;
    ans[(i + cou) % N] = Xs[index];
  }
  for(int an : ans){
    cout << an << endl;
  }
}


Measured memory_bytes: 4468
N = int(input())
A = [int(input()) for _ in range(N)]

A.sort()

ret1 = 0
i, j = 1, len(A) - 1
e1, e2 = A[0], A[0]
mode = 0

while i <= j :
    if i == j :
        ret1 += max(abs(e1-A[i]), abs(e2-A[i]))
        i += 1
    else :
        if mode == 0 :
            ret1 += abs(e1-A[j]) + abs(e2-A[j-1])
            e1, e2 = A[j], A[j-1]
            j -= 2
        else :
            ret1 += abs(e1-A[i]) + abs(e2-A[i+1])
            e1, e2 = A[i], A[i+1]
            i += 2
            
        mode ^= 1
        
ret2 = 0
i, j = 0, len(A) - 2
e1, e2 = A[-1], A[-1]
mode = 1

while i <= j :
    if i == j :
        ret2 += max(abs(e1-A[i]), abs(e2-A[i]))
        i += 1
    else :
        if mode == 0 :
            ret2 += abs(e1-A[j]) + abs(e2-A[j-1])
            e1, e2 = A[j], A[j-1]
            j -= 2
        else :
            ret2 += abs(e1-A[i]) + abs(e2-A[i+1])
            e1, e2 = A[i], A[i+1]
            i += 2
            
        mode ^= 1
        
print(max(ret1, ret2))

Measured memory_bytes: 50904
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,c=0;cin>>n;
  vector<int>a(n);
  for(int i=0;i<n;i++)cin>>a.at(i);
  for(int i=0;i<n;i++){
    if(a.at(a.at(i)-1)==i+1)c++;
  }
  cout<<c/2<<endl;
}


Measured memory_bytes: 640
{-# LANGUAGE BangPatterns #-}
import Control.Monad
import Data.Maybe
import Debug.Trace
import Data.List
import qualified Data.Map.Strict as Map
import qualified Data.IntMap.Strict as IntMap
import qualified Data.Set as Set
import qualified Data.IntSet as IntSet
import Data.Functor
import Data.Array

main :: IO ()
main = do
  (a:b:_) <- fmap (map read . words) getLine :: IO [Int]
  print $ solve a b

solve a b
  | b `mod` a == 0 = a + b
  | otherwise = b - a

Measured memory_bytes: 508
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<functional>
#include<algorithm>
#include<bitset>
#include<utility>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
using namespace std;
int a[100005],n;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>a[i];
	sort(a,a+n);
	cout<<abs(a[n/2-1]-a[n/2]);
	return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b,c=0,x=0,y=0;
long z=0;
cin >>a >>b;
x=b;
y=b;
while(1){
if (c==a) break;
if (c>0) {cin >> b;};
if (x>b) x=b;
if (y<b) y=b;
z+=b;
b=0;
c++;
};
cout<<x<<" "<<y<<" "<<z<<endl;
return 0;
}


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

const long long MOD = 1000000007;
const long long INF = 1LL << 60;
const int INT_INF = 1000000000;

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

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N;
  cin >> N;
  vector<ll> A(N);
  for (auto &it : A)
    cin >> it;
  sort(A.begin(), A.end());
  ll ans = 0;
  vector<ll> S(N);
  S[0] = A[0];
  for (int i = 1; i < N; i++)
  {
    S[i] += S[i - 1] + A[i];
  }
  ll now = 0;
  int l = 0, r = 1;
  while (r <= N - 1)
  {
    now = S[l];
    while (now * 2LL >= A[r] && r <= N - 1)
    {
      now += A[r];
      r++;
    }
    if (r == N)
    {
      ans = N - l;
      break;
    }
    cerr << "l: " << l << "r: " << r << endl;
    l = r;
    r++;
    if (r == N)
    {
      cout << 1 << endl;
      break;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1792
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <stack>
#include <math.h>
using namespace std;
//常に心してかかれ
//簡単なことを簡単にできるように練習する
//びっくりするくらいつまらないことで詰まってることも多い
int n;//問題で設定された呼び出し階層の深さ
class dot{
public:
	double x;
	double y;

	dot(double X,double Y){
		x=X;
		y=Y;
	}
};

void makeDots(dot A,dot B,int m){//m:この関数の呼び出し元の呼び出し階層
	double tmp_x;
	double tmp_y;

	tmp_x = A.x + (B.x - A.x)/3;
	tmp_y = A.y + (B.y - A.y)/3;

	dot P(tmp_x,tmp_y);

	tmp_x = sqrt(3.0)*(B.x - A.x) - (B.y-A.y);
	tmp_y = (B.x - A.x) + sqrt(3.0)*(B.y - A.y);
	tmp_x = tmp_x/(2*sqrt(3.0));
	tmp_y = tmp_y/(2*sqrt(3.0));
	tmp_x +=A.x;
	tmp_y +=A.y;

	dot Q(tmp_x,tmp_y);

	tmp_x = A.x + 2*(B.x - A.x)/3;
	tmp_y = A.y + 2*(B.y - A.y)/3;

	dot R(tmp_x,tmp_y);

	m++;
	if(m == n){
		cout <<A.x <<" " <<A.y <<endl;
		cout <<P.x <<" " <<P.y <<endl;
		cout <<Q.x <<" " <<Q.y <<endl;
		cout <<R.x <<" " <<R.y <<endl;
		return;
	}

	makeDots(A,P,m);
	makeDots(P,Q,m);
	makeDots(Q,R,m);
	makeDots(R,B,m);

}

int main(){
	dot A(0,0);
	dot B(100,0);

	cin >>n;

	if(n == 0){
		cout <<"0.00000000 0.00000000" <<endl;
		cout <<"100.00000000 0.00000000" <<endl;
		return 0;
	}
	makeDots(A,B,0);

	cout <<100 <<" " <<0 <<endl;
	return 0;
}

Measured memory_bytes: 1252
#include<iostream>
using namespace std;
int n;
long long l[10000001];
int main()
{
    cin>>n;
    l[0]=2;
    l[1]=1;
    for (int i=2;i<=n;i++)
        l[i]=l[i-1]+l[i-2];
    cout<<l[n]<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void){
    int N;
    scanf("%d", &N);

    int i,j;
    for(i=0; i<=N/4; i++) {
        for(j=0; j<=N/7; j++) {
            if(4*i + 7*j == N) {
                printf("Yes\n");
                return 0;
            }
        }
    }
    printf("No\n");
    return 0;
}

Measured memory_bytes: 128
"""
基本の方針は「各マンハッタン距離が何回足されるか」という考え方で距離の値を積み上げて行けばよい

まず、XとYは独立に考えることにする。
X軸の距離の方から積み上げる。
X1とX2の距離が足される回数は、
A.X1の列とX2の列の座標の組み合わせの数　×　B.その組み合わせが含まれるような座標の組み合わせの数
である。
A　＝　行数**２
B　＝　CMB(N*M-2 , K-2)である

同様の計算をY軸に関しても行えばよい。
"""
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

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

ans = 0

#X軸の距離を考える
A = M*M
B = cmb(N*M-2,K-2,p)
for i in range(1,N):
    ans += ((i*i)-(i-1+0)*i//2)*A*B%p
    ans %= p

#Y軸の距離を考える
A = N*N
B = cmb(N*M-2,K-2,p)
for i in range(1,M):
    ans += ((i*i)-(i-1+0)*i//2)*A*B%p
    ans %= p

print(ans)


Measured memory_bytes: 213040