akhauriyash/Code-Regression huggingface dataset:
import sys
input = sys.stdin.readline
N = int(input())
X = [[] for _ in range(N)]
P = [-1] * N
for i in range(N-1):
    a, b = map(int, input().split())
    X[a-1].append((i, b-1))
    #print(X)
    #P[b-1] = a-1
#print(X)

Q = [(0, -1)]
ANS = [-1] * (N-1)
cmax = 0
while Q:
    x, c0 = Q.pop()
    c = 1
    for i, y in X[x]:
        if c == c0: c += 1
        ANS[i] = c
        Q.append((y, c))
        c += 1
    cmax = max(cmax, c-1)

print(cmax)
for ans in ANS:
    print(ans)

Measured memory_bytes: 27732
#include <iostream>

using namespace std;
int main()
{

    int r,m,a;
    cin>>r>>m>>a;
    if((r==5 && m==5 &&a==7)|| (r==7 && m==5 &&a==5) || (r==5 && m==7 &&a==5))
    {
        cout<<"YES";
    }
    else{
        cout<<"NO";
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
constexpr int MOD = 1000000007;
constexpr int INF = 2147483647;
int main()
{
    int N;
    cin >> N;
    cout << (N+1) / 2 << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <bits/stdc++.h>
using namespace std;
typedef long double ll;

int Array(int x[],int n){
    for(int i=0;i<n;i++){
        cin >> x[i] ;
    }
    return *x;
}

int main(){
    int n,k;
    cin >> n >> k;
    int p[n];
    vector<ll> ktit(n);
    vector<ll> riskw(n+1);
    Array(p,n);
    ll sum=0;
    ll ans=0;
    
    for(int i=0;i<n;i++){
        ll s=(p[i]+1);
        s/=2;
        ktit.push_back(s);
        riskw[i+1]=s;
    }

    for(int i=1;i<=n;i++){
        riskw[i]+=riskw[i-1];
    }

    for(int i=k;i<=n;i++){
        ll x=riskw[i]-riskw[i-k];
        if(x>ans){
            ans=x;
        }
    }
    cout <<setprecision(8)<< ans << endl;
}

Measured memory_bytes: 12032
from fractions import gcd
from functools import reduce

def lcm(x, y):
    return x * y // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

def sub_by_2(n):
    cnt = 0
    while n % 2 == 0:
        cnt += 1
        n //= 2
    return cnt

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

lcm_2 = [sub_by_2(v // 2) for v in A]
if all(lcm_2[0] == v for v in lcm_2):
    num = lcm_list([v // 2 for v in A])
    ans = M // num
    print(ans // 2 + ans % 2)
else:
    print(0)


Measured memory_bytes: 93408
#include <iostream>
#include <array>
#include <algorithm>

using namespace std;

int main() {
	array<int, 10> input;
	for(auto& i : input)
		cin >> i;
	sort(input.begin(), input.end(), greater<int>());
		cout << input[0] << endl
			 << input[1] << endl
			 << input[2] << endl;;
	return 0;
}

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

using ll = long long;
using pii = pair<int, int>;

#define vt          vector
#define sz(x)       (int)(x).size()
#define all(x)      (x).begin(), (x).end()
#define rall(x)     (x).rbegin(), (x).rend()
#define fi          first
#define se          second

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);

    int n, m;
    cin >> n >> m;
    vt<bool> vis(n);
    int oddSize = (m + 1) / 2 * 2,
        evenSize = m / 2 * 2 + 1;
    for (int i = 0; i < m; i++) {
        int x = i / 2;
        if (~i & 1) cout << x + 1 << ' ' << oddSize - x << '\n';
        else cout << n - evenSize + x + 1 << ' ' << n - x << '\n';
    }
}


Measured memory_bytes: 3660
#include<iostream>
using namespace std;
int main(){
	int x,y;
	cin>>x>>y;

	if(4*x>=y&&y>=2*x){
		if(y%2==0){
			cout<<"Yes";
			
		}
		else cout<<"No";
	}
	else cout<<"No";
	return 0;
}

Measured memory_bytes: 3620
S = input()

if len(S) == 1:
    print(int(S))
    exit()

ans = 0
pluses = [""]*(len(S)-1)
for i in range(2 ** (len(S) - 1)):
    for j in range(len(S)-1):
        if (i >> j) & 1:
            pluses[j] = "+"
        else:
            pluses[j] = ""  
    Ss = ""
    for k, p in zip(S[:-1], pluses):
        Ss += k + p
    Ss += S[-1]
    ans += eval(Ss)
print(ans)

Measured memory_bytes: 3064
// @prefix atcoder
// @description atcoder template

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

// typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;

// rep
//------------------------------------------
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) (x).begin(), (x).end()
#define DEBUG(x) cerr << #x << ": " << x << '\n'
#define DEBUGP(x) cerr << #x << ": " << x.first << " \t" << x.second << '\n'

int n, k;
VP v;
signed main() {
    cin >> n >> k;
    k--;

    REP(i, n) {
        int a, b;
        cin >> a >> b;
        v.push_back(make_pair(a, b));
    }

    sort(ALL(v), [](PII x, PII y) {
        return x.first < y.first;
    });

    int now = 0;
    FOR(i, 0, n) {
        if (now <= k && k < v[i].second + now) {
            cout << v[i].first << endl;
            return 0;
        }
        now += v[i].second;
    }
    return 0;
}


Measured memory_bytes: 2420
#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int H,W,h,w;
int ans[601][601];

int main(void){
	scanf("%d%d%d%d",&H,&W,&h,&w);
	if(H%h==0 && W%w==0){
		puts("No");
		return 0;
	}
	if(W%w!=0){
		int c=W/w+1;
		int r=W-c;
		ll b=50000;
		ll a=b*(w-1)-1;
		for(int i=0;i<H;i++){
			for(int j=0;j<W;j++){
				if(j%w==0)ans[i][j]=a;
				else ans[i][j]=-b;
			}
		}
	}else{
		int c=H/h+1;
		int r=H-c;
		ll b=50000;
		ll a=b*(h-1)-1;
		for(int i=0;i<W;i++){
			for(int j=0;j<H;j++){
				if(j%h==0)ans[j][i]=a;
				else ans[j][i]=-b;
			}
		}
	}
	puts("Yes");
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			printf("%d%c",ans[i][j],j+1==W?'\n':' ');
		}
	}
	return 0;
}

Measured memory_bytes: 3200
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,s,n) for(int i=(s); i<(n); i++)
#define all(v) v.begin(),v.end()
#define outve(v) for(auto i : v) cout << i << " ";cout << endl
#define outmat(v) for(auto i : v){for(auto j : i) cout << j << " ";cout << endl;}
#define in(n,v) for(int i=0; i<(n); i++){cin >> v[i];}
#define out(n) cout << (n) << endl
#define fi first
#define se second
#define pb push_back
#define mod 1000000007
#define infi 1900000000
#define infl 1100000000000000000
#define cyes cout << "Yes" << endl
#define cno cout << "No" << endl
#define csp << " " <<
#define outset(n) cout << fixed << setprecision(n);
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T> using ve = vector<T>;
template<typename T> using pq2 = priority_queue<T>;
template<typename T> using pq1 = priority_queue<T,vector<T>,greater<T>>;




int main()
{
    int N,Q;
    cin >> N >> Q;
    pq1<pair<pii,int>> A;
    rep(i,N){
        int s,t,x;
        cin >> s >> t >> x;
        s = max(s-x,0);
        t = max(t-x,0);
        A.push({{s,t},x});
    }
    
    vi D(Q);
    in(Q,D);
    pq1<pii> B;
    set<pii> C;
    
    
    rep(i,Q){
        int d = D[i];
        
        while (!A.empty()) {
            auto a = A.top();
            if(a.fi.fi <= d){
                B.push({a.fi.se,a.se});
                C.insert({a.se, a.fi.se});
                A.pop();
            }else{
                break;
            }
        }
        
        while (!B.empty()) {
            auto b = B.top();
            if(b.fi <= d){
                C.erase({b.se,b.fi});
                B.pop();
            }
            else break;
        }
        
        if(C.empty()) D[i] = -1;
        else D[i] = (*begin(C)).fi;
        
        
        
    }
    
    outve(D);
    //rep(i,Q) cout << D[i] << endl;
    
    
    
    

    return 0;
}


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

#define endl "\n"
#define all(x) x.begin(),x.end()
#define pb push_back
#define ff first 
#define ss second 
#define pii pair<int,int>
#define vi vector<int>
#define vc vector<char>
#define vii vector<pii>
#define vvi vector<vi>
#define fori(i,n) for(int i=1;i<=n;++i)
#define forn(i,n) for(int i=0;i<n;++i)
#define sz(x) int(x.size())
#define error(x) cout<<#x<<" "<<x<<endl
#define IOS  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

const int N=100*1000;
const int mod=1e9+7;

int min3(int a,int b,int c){return min(a,min(b,c));}
int max3(int a,int b,int c){return max(a,max(b,c));}
int min4(int a,int b,int c,int d){return min(min(a,b),min(c,d));}
int max4(int a,int b,int c,int d){return max(max(a,b),max(c,d));}

//#define int int64_t
//int a[N+2];

int32_t  main(){
	IOS;
  string s;cin>>s;
  //check if it can be in form of YYMM
  bool yymm=false;
  int a=s[0]-'0';
  int b=s[1]-'0';
  int c=s[2]-'0';
  int d=s[3]-'0';
  int num=10*c+d;
  if(num>0 && num<=12)yymm=true;
  bool mmyy=false;
  num=10*a+b;
  if(num>0 && num<=12)mmyy=true;
  if(yymm && mmyy){
    cout<<"AMBIGUOUS\n";
  }else if(yymm==true && mmyy==false){
    cout<<"YYMM\n";
  }else if(!yymm && mmyy){
    cout<<"MMYY\n";
  }else cout<<"NA"<<endl;

  return 0;
}



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

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

    std::vector<int> d(n);
    for (auto&& di : d) std::cin >> di;

    std::sort(d.begin(), d.end());

    const auto n2 = n/2;
    std::cout << (d[n2] == d[n2 - 1] ? 0 : d[n2] - d[n2-1]) << std::endl;
}

Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<vector>
#include<climits>
#include<map>
#include<string>
#include<functional>
#include<iomanip>
#include<deque>
#include<random>
#include<set>
#include<bitset>
#include<cassert>

using namespace std;
typedef long long ll;
typedef double lldo;
#define mp make_pair
#define pub push_back
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
ll gcd(ll a, ll b) { if (a % b == 0) { return b; } else  return gcd(b, a % b); }
ll lcm(ll a, ll b) { if (a == 0) { return b; }return a / gcd(a, b) * b; }
template<class T>ll LBI(vector<T>& ar, T in) { return lower_bound(ar.begin(), ar.end(), in) - ar.begin(); }
template<class T>ll UBI(vector<T>& ar, T in) { return upper_bound(ar.begin(), ar.end(), in) - ar.begin(); }

ll k, ans = 0;

int main() {
	cin >> k;
	rep(i, k) {
		rep(j, k) {
			rep(l, k)ans += gcd(i + 1, gcd(j + 1, l + 1));
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3624
N = int(input())
A = list(map(int, input().split()))
iter_A = iter(A)
ans = 0
for i in range(1, len(A)):
    if A[i-1] > A[i]:
        ans += A[i-1] - A[i]
        A[i] = A[i-1]
print(ans)

Measured memory_bytes: 32072
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>0;--i)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define Vi vector<int>
#define pb push_back
#define i197 1000000007
#define MAX_N 200002
using namespace std;

typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<Pii,int> Piii;
typedef pair<ll,int> Pli;
typedef pair<string,string> Pss;
const int inf=1000000000;
struct edge{
	int myc,to,c,cost;
};
struct pos{
	int to,cost,color;
};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
int th[3001][3001]={};
int main() {
	int n,m;
	cin>>n>>m;
	Vi v,h;
	int vt=0;
	Vi dp(n+1,0);
	v.push_back(0);
	h.push_back(0);
	rep(i,n){
		int v1,h1;
		cin>>v1>>h1;
		vt+=v1;
		v.push_back(vt);
		h.push_back(h1);
	}
	rep(i,n){
		th[i+1][i+1]=h[i+1];
		for(int j=i+2;j<n+1;++j){
			th[i+1][j]=th[i+1][j-1]+h[j]+abs(h[j]-h[j-1]);
		}
	}
	int t1,s1;
	cin>>t1>>s1;
	rrep(j,n+1){
		if(v[j]>t1)continue;
		dp[j]=th[1][j];
		if(dp[j]<s1)dp[j]=-1;
	}
	dp[0]=-1;

	for(int i=1;i<m;++i){
		cin>>t1>>s1;
		rrep(j,n+1){
			if(v[j]>t1)continue;

			if(dp[j]==0){
				rep(k,j){
					if(dp[k]==-1)continue;
					dp[j]=max(dp[j],dp[k]+th[k+1][j]);
				}
			}
			if(dp[j]<s1)dp[j]=-1;
		}
//		cout<<i<<endl;
//		rep(j,n+1)cout<<dp[j]<<endl;
	}
	bool flg=false;
	int res=-1;
	rrep(i,n+1){
		if(dp[i]>0){
			flg=true;
			res=max(res,t1-v[i]);
		}
	}
	if(flg){
		cout<<res<<endl;
	}else{
		cout<<"-1"<<endl;
	}
	return 0;
}



Measured memory_bytes: 30736
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>

using namespace std;

int main(){
    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    for(int i=0; i<H; i++) cin >> S[i];

    vector<vector<int>> A(H, vector<int>(W, 0));
    for(int i=0; i<H; i++){
        for(int j=0; j<W; j++){
            if(S[i][j]=='#'){
                if(i<H-1) A[i+1][j] += 1;
                if(j<W-1) A[i][j+1] += 1;
                if(i>0) A[i-1][j] += 1;
                if(j>0) A[i][j-1] += 1;
                if(i<H-1 && j<W-1) A[i+1][j+1] += 1;
                if(i>0 && j>0) A[i-1][j-1] += 1;
                if(i>0 && j<W-1) A[i-1][j+1] += 1;
                if(i<H-1 && j>0) A[i+1][j-1] += 1;
            }
        }
    }
    for(int i=0; i<H; i++){
        for(int j=0; j<W; j++){
            if(S[i][j] == '#') cout << '#';
            else cout << A[i][j];
        }
        cout << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
	long long a1, m1, a2, m2, a3, m3;
	while (true) {
		cin >> a1 >> m1 >> a2 >> m2 >> a3 >> m3;
		if (a1 + m1 + a2 + m2 + a3 + m3 == 0) {
			break;
		}
		long long a = 0, b = 0, c = 0;
		long long x1 = 1, y1 = 1, z1 = 1;
		while (x1 != 1||a==0) {
			x1 = (a1*x1) % m1;
			a++;
		}
		while (y1 != 1||b==0) {
			y1 = (a2*y1) % m2;
			b++;
		}
		while (z1 != 1||c==0) {
			z1 = (a3*z1) % m3;
			c++;
		}
		long long a2 = min(a,b), b2 = max(a,b), c2 = c;
		while (a != 0) {
			int c = b;
			b = a;
			a = c%a;
		}
		b = (b*(a2 / b)*(b2 / b));
		b2 = b;
		a = min(c, b);
		b = max(b, c);
		while (a != 0) {
			int c = b;
			b = a;
			a = c%a;
		}
		b = (b*(c2 / b)*(b2 / b));
		cout << b << endl;
	}
}

Measured memory_bytes: 3072
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    int n,l;
    cin>>n>>l;
    vector<string>s(n);
    for(int i=0;i<n;i++)
    {
        cin>>s[i];
    }
    sort(s.begin(),s.end());
    for(int i=0;i<s.size();i++)
    {
        cout<<s[i];
    }
}

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

int main() {
  int N,M,x;
  cin>>N>>M;
  vector<int> c(N); 
  for(int i=0;i<M;i++){
    cin>>x;
  c.at(x-1)++;
      cin>>x;
  c.at(x-1)++;
  }
  for(int i=0;i<N;i++){
    cout<<c.at(i)<<endl;
}
}


Measured memory_bytes: 256
import std.stdio;
import std.string;
import std.conv;
//import std.typecons;
import std.algorithm;
import std.array;

void main() {
	auto data = split(readln());
	auto N = data[0].to!int(), M = data[1].to!int();
	int[] X = split(readln()).map!(x => to!int(x)).array.sort().array;
	
	if (N >= M) { writeln("0"); return; }
	
	int[] d;
	foreach (i; 0 .. M-1) { d ~= X[i+1] - X[i]; }
	d = sort(d).array;
	writeln( reduce!"a+b"(d[0 .. M-N]) );
	
}


Measured memory_bytes: 4360
N, X = map(int, input().split())
hight, paty = [0]*51, [0]*51
hight[0] = 1
paty[0] = 1

for i in range(1, 51):
	hight[i] = 2*hight[i-1] + 3
	paty[i] = 2*paty[i-1] + 1

def f(n, x):
	if x == 0: return 0
	elif n == 0: return 1

	elif x <= (hight[n-1]+1):
		return f(n-1, x-1)
	else:
		return paty[n-1] + 1 + f(n-1, x-hight[n-1]-2)

print(f(N, X))

Measured memory_bytes: 3064
N = int(input())
F = [[int(i) for i in input().split()] for j in range(N)]
P = [[int(i) for i in input().split()] for k in range(N)]
x = -(10**10)
for i in range(1,2**10):
    L = [int(b) for b in '{:0>10}'.format(str(bin(i))[2:])]
    y = 0
    for n in range(N):
        m = sum([l&f for l, f in zip(L, F[n])])
        y += P[n][m]
    x = max(x, y)
print(x)


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

int main() {
  int n,m;
  cin >> n >> m;
  multiset<long> price;
  
  for (int i=0; i<n; i++){
    long a;
    cin >> a;
    price.insert(a);
  }
  
  for (int i=0; i<m; i++){
    auto maxitr = --price.end();
    long old_max = *maxitr;
    price.erase(maxitr);
    long new_max = floor(old_max/2);
    price.insert(new_max);
  }
  long sum = 0;
  for(auto itr = price.begin(); itr != price.end(); ++itr) {
      sum += *itr;
  }
  cout << sum << endl;

}

Measured memory_bytes: 4992
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define mp make_pair
#define ins insert
#define sb substr
#define con continue
#define ub upper_bound
#define lb lower_bound
#define sp fixed<<setprecision
#define bp __builtin_popcountll
#define pll pair<ll,ll>
#define pld pair<ld,ld>
using namespace std;

ll power(ll x, ll y);
ll mpower(ll x, ll y, ll p);
ll modInv(ll a, ll m);
ll gcdExtended(ll a, ll b, ll *x, ll *y);
bool isPrime(ll n);

ll A[1000001];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t,i,j,k,l,h,p,q,r,x,y,z,a,b,c,d,f,n,m,M=1000000007;
    char ch,ch2,ch3;
    string s,s1,s2,s3;
    vector<ll> v,w;
    unordered_map<ll,ll> N;
    set<ll> S;
    set<ll> :: iterator itr;
    cin>>x>>y;
    p=__gcd(x,y);
    for(i=2;i<1000001;i++){
        if(!A[i]){
            for(j=i+i;j<1000001;j+=i){
                A[j]=1;
            }
        }
    }
    c=1;
    for(i=2;i<1000001;i++){
        if(A[i]){
            con;
        }
        if(p%i==0){
            c++;
            while(p%i==0){
                p/=i;
            }
        }
    }
    if(p>1){
        c++;
    }
    cout<<c;
    return 0;
}

ll modInv(ll a, ll m){
    ll x, y;
    ll g = gcdExtended(a, m, &x, &y);
    ll res = (x%m + m) % m;
    return res;
}

ll gcdExtended(ll a, ll b, ll *x, ll *y){
    if (a == 0){
        *x = 0, *y = 1;
        return b;
    }
    ll x1, y1;
    ll gcd = gcdExtended(b%a, a, &x1, &y1);
    *x = y1 - (b/a) * x1;
    *y = x1;
    return gcd;
}

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

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

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


Measured memory_bytes: 8064
#include<stdio.h>
int n, d[101], t, cnt;

int main() {
    scanf("%d", &n);
    for(int i=0; i<n; i++) {
        scanf("%d", &t);
        if(!d[t]) cnt++;
        d[t]=1;
    }

    printf("%d", cnt);

    return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef ll Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
//#define mt make_tuple
//typedef tuple<pii,int,int> tp;
//typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
//template<class C>constexpr int size(const C &c){return (int)c.size();}
//template<class T,size_t N> constexpr int size(const T (&xs)[N])noexcept{return (int)N;}
const double PI=acos(-1);
const double EPS=1e-7;
Def inf=sizeof(Def)==sizeof(long long)?2e18:1e9;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int main(){
	int n;
	cin>>n;
	string s;
	cin>>s;
	int mi=0,co=0;
	rep(i,s.size()){
		if(s[i]=='(')co++;
		else co--;
		mi=min(mi,co);
	}
	rep(i,max(0,-mi))s="("+s;
	rep(i,max(0,co-mi))s+=")";
	cout<<s<<endl;
}










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

int main(void){
  	int n;
    int is7 = 0;
    int is5 = 0;

    for(int i = 0; i < 3; i++){
        cin >> n;
        if(n == 5) is5++;
        else if(n == 7) is7++;
    }

    cout << ((is5 == 2 && is7 == 1) ? "YES" : "NO") << endl;
    return 0;
}

Measured memory_bytes: 256
#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 MD = (int)1e9 + 7; typedef vector<ll> VL;
void dbg(){ cerr << "\n"; }  template <class T, class ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }
template <class T> void amax(T& a,T b){ a=max(a,b);}


vector<bool> eratos ( int n){
	vector<bool> prime(n+20, 0);
	prime[2] = true; prime[0] = prime[1] = false;
	for(int i = 3; i <= n; i += 2) prime[i] = true, prime[i+1] = false;
	int limit = (int)sqrt((double)n) + 1;
	for(int i = 3; i <= limit; i += 2){
		if(!prime[i]) continue;
		for(int j = i * i, k = i * 2; j <= n; j += k) prime[j] = false;
	}
	return prime;
}

int main() {
	//cin.tie(0); ios_base::sync_with_stdio(false);
	auto pr = eratos(150000);
	int x, ans =0;
	cin >>x;
	//for(auto x :pr) cerr<<x<<" "; cerr<<"\n";
	
	for(int i=x; ;i++){
		if(pr[i] ==true){ cout <<i <<"\n"; break;}
	}
	return 0;
}



Measured memory_bytes: 256
import sys
if sys.version_info[0]>=3: raw_input=input
cross=lambda a1, b1, a2, b2: a1*b2-a2*b1
try:
	T=0
	while True:
		T+=1
		n=int(raw_input())
		if n==0: break
		a=[[float(e) for e in raw_input().split()] for i in range(n)]
		s=0
		t=0
		for i in range(n-1):
			x=cross(a[i][0],a[i][1],a[i+1][0],a[i+1][1])
			if x>0: s+=abs(x)/2
			else: t+=abs(x)/2
		x=cross(a[n-1][0],a[n-1][1],a[0][0],a[0][1])
		if x>0: s+=abs(x)/2
		else: t+=abs(x)/2
		print('%d %.1f'%(T,abs(s-t)))
		raw_input()
except EOFError:
	pass

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvl;

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  ll n, k;
  cin >> n >> k;
  string s;
  cin >> s;
  vll v;
  int c = 0;
  char now = '1';
  for (int i = 0; i < n; i++) {
    if (now == s[i]) {
      c++;
    } else {
      v.push_back(c);
      c = 1;
      now = s[i];
    }
  }
  v.push_back(c);
  v.push_back(0);
  ll sum = 0;

  ll m = v.size();
  for (int i = 0; i < 2 * k + 1 && i < m; i++) {
    sum += v[i];
  }
  ll ans = sum;
  for (int j = 0; j < m - 2 * k - 1; j++) {
    sum -= v[j];
    sum += v[j + 2 * k + 1];
    if (j % 2 == 1)
      ans = max(ans, sum);
  }
  cout << ans << endl;
  return 0;
}


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

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

    int n, m, sum = 0;
    cin >> n >> m;
    vector<int> h(n), a(m), b(m), c(n, 0);
    rep(i, n) cin >> h.at(i);
    rep(j, m)
    {
        cin >> a.at(j) >> b.at(j);
        if (h.at(a.at(j) - 1) <= h.at(b.at(j) - 1))
            c.at(a.at(j) - 1)++;
        if (h.at(a.at(j) - 1) >= h.at(b.at(j) - 1))
            c.at(b.at(j) - 1)++;
    }
    rep(i, n) if (c.at(i) == 0) sum++;
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 4772
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define _USE_MATH_DEFINES
#include <math.h>
#define rep(i,n) for(int i = 0;i < n;i++)
#define NIL = -1;

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

ll lcm(ll a,ll b){
    a / gcd(a,b) * b;
}
const ll mod = 1e9 + 7;

int main(){
    int n;
    string s;
    cin >> n >> s;
    
    int ans = 0;

    for (int i = 0;i < 1000;i++){
        vector<int> pin(3);
        pin[0] = i / 100;
        pin[1] = i / 10 % 10;
        pin[2] = i % 10;
        int k = 0;
        for (int j = 0;j < n;j++){
            if (s[j] - '0' == pin[k]){
                k++;
            }

            if (k == 3){
                ans++;
                break;
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define p pair<ll,ll>
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int main()
{
      
       ll a,b,x,y,ans=0;
       cin>>a>>b;
       for(int i=1;i<=b;i++)
        {
            cin>>x;ans+=x;
        }
        ans= a-ans>=0? a-ans:-1;
        cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 3640
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ii pair<int, int>
#define vi vector<int>
#define vii vector<ii>
#define vvi vector<vector<int>>
#define vvii vector<vector<ii>>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define uni(v) v.erase(unique(v.begin(), v.end()), v.end())
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (ll) a / __gcd(a, b) * b
#define what_is(x) cerr << #x << " is " << x << endl;

using namespace std;

void write();
template <typename T, typename... Args>
void write(T x, Args... args);
template <typename T>
void print_all(vector<T>& a);

void solve() {
    char c;
    cin >> c;
    write(c > 96 ? 'a' : 'A');
}

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

    int t = 1;
    // cin >> t;
    while (t--) solve();

    return 0;
}

void write() { cout << "\n"; }
template <typename T, typename... Args>
void write(T x, Args... args) {
    cout << x << ' ';
    write(args...);
}
template <typename T>
void print_all(vector<T>& a) {
    for (int i = 0; i < a.size(); ++i) cout << a[i] << " \n"[i == a.size()-1];
}


Measured memory_bytes: 3600
#include<stdio.h>

int n,d;
int dp[205][205];
//dp[a][b] .. a日目にb番目の服を着るような状態のうち、得られる得点の最大値。着れなければ十分小さい数

int hukup[205];
int hukdw[205];
int hukha[205];
int ond[205];


int inf = -1000000;

int abs(int p){
	if(p<0)return -p;
	else return p;
}

int max(int p,int q){
	if(p<q)return q;
	return p;
}

int main(void){
	scanf("%d%d",&d,&n);
	for(int i=1;i<=d;i++){
		scanf("%d",&ond[i]);
	}
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&hukdw[i],&hukup[i],&hukha[i]);
	}
	//入力の受付ここまで
	
	for(int j=1;j<=n;j++){
		if(hukdw[j]<=ond[1] && ond[1]<=hukup[j]){
			dp[1][j] = 0;
		}
		else{
			dp[1][j] = inf;
		}
	}
	//初日を初期化。
	
	for(int i=2;i<=d;i++){
		for(int j=1;j<=n;j++){
			//i日目に、j番目の服を着るときの最大値
			if(hukdw[j]<=ond[i] && ond[i]<=hukup[j]){
				//着られる
				dp[i][j]=0;
				for(int k=1;k<=n;k++){
					//現在の最大値と、(前日にkを着て、今日jを着るようなパターン) のうち、大きい方をとっていく
					dp[i][j] = max(dp[i][j] , dp[i-1][k] + abs(hukha[j]-hukha[k]) );
				}
			}
			else{
				//着られない
				dp[i][j] = inf;
			}
		}
	}
	
	int ans = 0;
	for(int j=1;j<=n;j++){
		//最終日のうちの、最大値
		ans = max(ans,dp[d][j]);
	}
	printf("%d\n",ans);
	return 0;
}

	
	
	

Measured memory_bytes: 1196
#include <iostream>
#include <vector>
#include <cstdlib>  
#include <algorithm>
#include<string>

using namespace std;
 
int main() {
    long a,b,k;
    cin >> a>>b>>k;
    long moto = a;
    a = a-k;
  
    if(a <=0) {
      long sin = k-moto;
      a = 0;
      
      b = b-sin;
      if(b <= 0) {b = 0;}
      cout<<a<<" "<<b;
      //return 0;
    }
    else if(a > 0){
      cout<<a<<" "<<b;
      //return 0;
    }
  
  
}

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

int main(){
	
	long long n, m;
	cin >> n >> m;

	long long ans = 0;
	if(n == 1 && m == 1) ans = 1;
	else if(min(n,m) == 1) ans = max(n, m) - 2;
	else if(n > 2 && m > 2) ans = (n-2) * (m-2);

	cout << ans << endl;
	

	return 0;
}

Measured memory_bytes: 256
<?php
  list($h, $w) = explode(" ", trim(fgets(STDIN)));

  $a = [];
  for($i=0;$i<$h;$i++){
    list($a[]) = explode(" ", trim(fgets(STDIN)));
  }

  for($i=0;$i<$w+2;$i++){
    echo "#";
  }
  echo PHP_EOL;
  for($i=0;$i<$h;$i++){
    echo "#";
    echo $a[$i];
    echo "#".PHP_EOL;
  }
  for($i=0;$i<$w+2;$i++){
    echo "#";
  }


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

int main(){
    int n,m;
    map<string, int> mp;
    cin >> n;
    for (int i=0;i<n;i++) {
        string s;
        cin >> s;
        mp[s]++;
    }
    cin >> m;
    for (int i=0;i<m;i++){
        string s;
        cin >> s;
        mp[s]--;
    }
    int ans = 0;
    for (auto x:mp){
        ans = max(ans, x.second);
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
// J'aime
// Chemise Blanche

#include <bits/stdc++.h>
using namespace std;

#define int long long

#define ii pair<int,int>
#define fi first
#define sc second

#define all(x) (x).begin(),(x).end()
#define dbg(x) cerr << __LINE__ << " > " << #x << " = " << (x) << endl

void MAIN() {
  int n, k;
  cin >> n >> k;
  int t = 1;
  for (int i = 0; i < n; i++) {
    t = min(t * 2, t + k);
  }
  cout << t << '\n';
}

signed main() {
#ifdef _DEBUG
  // freopen("in" , "r", stdin );
  // freopen("out", "w", stdout);
#endif
  ios::sync_with_stdio(0); cin.tie(0);
  int T = 1;
  // cin >> T;
  while (T--) MAIN();
}


Measured memory_bytes: 3656
<?php

while (TRUE) {
    $c = fscanf(STDIN, '%d,%d,%d,%d,%d');
    if (feof(STDIN)) {
        break;
    }
    sort($c);
    $hash = array();
    $max = 0;
    foreach ($c as $v) {
        if (!isset($hash[$v])) {
            $hash[$v] = 0;
        }
        $hash[$v]++;
        $max = $hash[$v] > $max ? $hash[$v] : $max;
    }
    arsort($hash);
    $combo = 'null';
    if ($max >= 2) {
        $combo = 'one pair';
    }
    if ($max >= 2 && count($hash) <= 3) {
        $combo = 'two pair';
    }
    if ($max >= 3) {
        $combo = 'three card';
    }
    if (count($hash) === 5 && isStraight($c)) {
        $combo = 'straight';
    }
    if ($max >= 3 && count($hash) <= 2) {
        $combo = 'full house';
    }
    if ($max >= 4) {
        $combo = 'four card';
    }
    echo $combo . PHP_EOL;
}

function isStraight($cards) {
    if (max($cards) - min($cards) === 4) {
        return true;
    }
    if ($cards[0] === 1 && $cards[1] === 10 && $cards[4] === 13) {
        return true;
    }
    return false;
}

Measured memory_bytes: 6692
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A;
  cin >>A;
  
  long sum = 0;
  
  for(int i=0;i<=A;i++){
   if(i%3 ==0){
   }
   else if(i%5==0){
   }
   else
    sum +=i; 
  }
 
    cout << sum << endl;
}
 

Measured memory_bytes: 3632
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int INF = (int)1e9 + 7;

int main() {
    int n, k; cin >> n >> k;
    vector<int> a(n);
    for (auto &ai: a) cin >> ai;
    int mi = INF;
    for (int i = 0; i + k <= n; i++) {
        int l = a[i], r = a[i + k - 1];
        mi = min(mi, min(abs(l), abs(r)) + r - l);
    }
    cout << mi << endl;
    return 0;
}


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

#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") //Optimization flags
#pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX
#pragma GCC target("avx2") //Enable AVX

using namespace std;

#define F first
#define S second 

#ifdef __debug_leywar
#include <debug/debugger.h>
#else
#define db(...) ;
#endif

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
  
    int n ; 
    cin >> n ;

    cout << ( n >= 30 ? "Yes" : "No" ) ;

    return 0;
}

Measured memory_bytes: 3636
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<bitset>
using namespace std;
#define ll long long
#define re register
#define mp make_pair
typedef pair<int,int> pii;
inline int gi()
{
	int sum=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
	return f*sum;
}
int main()
{
	int n=gi();int ans=0,mx=0;
	for(int i=1;i<=n;i++)
	{
		int x=gi();
		mx=max(mx,x);ans+=x;
	}
	ans-=mx/2;printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
using System.Diagnostics;

class Myon
{
    public Myon() { }
    public static int Main()
    {
        new Myon().calc();
        return 0;
    }

    Scanner cin;
    Func cin2;
    void calc()
    {
        cin = new Scanner();
        cin2 = new Func();
        int N=cin.nextInt();
        if(N%2!=0)N++;
        N=N/2;
        Console.WriteLine(N);
        
    }
}



class Scanner
{
    string[] s;
    int i;

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

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

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

    public int nextInt()
    {
        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0)
    {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextInt() + add;
        }
        return Array;
    }

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

    public long[] ArrayLong(int N, long add = 0)
    {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextLong() + add;
        }
        return Array;
    }

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


    public double[] ArrayDouble(int N, double add = 0)
    {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextDouble() + add;
        }
        return Array;
    }
}

class Answer
{
    public void Int2DArrayAns(int[,]x,char c)
    {
        for(int i=0;i<x.GetLength(0);i++)
        {
            for(int j=0;j<x.GetLength(1)-1;j++)
            {
                Console.Write(x[i,j]);
                Console.Write(c);
            }
            Console.WriteLine(x[i,x.GetLength(1)-1]);
        }
    }
    public void Char2DArrayAns(char[,]x,char c)
    {
        for(int i=0;i<x.GetLength(0);i++)
        {
            for(int j=0;j<x.GetLength(1)-1;j++)
            {
                Console.Write(x[i,j]);
                Console.Write(c);
            }
            Console.WriteLine(x[i,x.GetLength(1)-1]);
        }
    }
}

class Func
{
    public long GCDLong(long a, long b)
    {
        while(a!=0)
        {
          long t=a;
          a=b%a;
          b= t;
        }
      
        return b;        
    }
}

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

// @@ !! LIM()

int main(/* int argc, char *argv[] */) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);

  ll A, B, C, D; cin >> A >> B >> C >> D;

  if (A + B > C + D) {
    cout << "Left\n";
  }else if (A + B < C + D) {
    cout << "Right\n";
  }else {
    cout << "Balanced\n";
  }

  return 0;
}



Measured memory_bytes: 3592
R,C,K = map(int,input().split())
dp0 = [[0 for _ in range(C+1)] for f in range(R+1)]
dp1 = [[0 for _ in range(C+1)] for f in range(R+1)]
dp2 = [[0 for _ in range(C+1)] for f in range(R+1)]
dp3 = [[0 for _ in range(C+1)] for f in range(R+1)]
vl = [[0 for _ in range(C+1)] for f in range(R+1)]

for i in range(K):
	r,c,v = map(int,input().split())
	vl[r][c] = v

for i in range(1, R+1):
	for j in range(1, C+1):
		dp0[i][j] = max(dp0[i][j], dp0[i-1][j], dp1[i-1][j], dp2[i-1][j], dp3[i-1][j])
		dp3[i][j] = max(dp3[i][j], dp3[i][j-1], dp2[i][j-1]+vl[i][j], dp2[i][j]+vl[i][j])
		dp2[i][j] = max(dp2[i][j], dp2[i][j-1], dp1[i][j-1]+vl[i][j], dp1[i][j]+vl[i][j])
		dp1[i][j] = max(dp1[i][j], dp1[i][j-1], dp0[i][j-1]+vl[i][j], dp0[i][j]+vl[i][j])

print(max(dp0[R][C], dp1[R][C], dp2[R][C], dp3[R][C]))

Measured memory_bytes: 472084
x_list = []

n = int(input())
s = str(input())
x = 0
x_list.append(x)

for i in s:
    if i == "I":
        x += 1
        x_list.append(x)
    else:
        x -= 1
        x_list.append(x)

print(max(x_list))

Measured memory_bytes: 3060
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define pi acos(-1.0)

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;


struct edge{
    int to;
    int cost;
};

vector<edge> tree[100001];
ll cost[100001];

void dfs(int v, int p, ll c){
    cost[v] = c;
    for(auto &edge : tree[v]){
        if(edge.to == p) continue;
        dfs(edge.to, v, c + edge.cost);
    }
}


int main(){
    cin.tie(0);
   	ios::sync_with_stdio(false);
    int n;
    int q, k;
    cin >> n;
    REP(i, n - 1){
        int a, b, c;
        cin >> a >> b >> c;
        tree[a].push_back({b, c});
        tree[b].push_back({a, c});
    }
    cin >> q >> k;
    dfs(k, 0, 0);
    REP(i, q){
        int x, y;
        cin >> x >> y;
        cout << cost[x] + cost[y] << endl;
    }

    return 0;
}



Measured memory_bytes: 12800
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f3f;
const int mod = 1e9+7;
const int maxn = 1e5+500;
ll T,n,m;
int a[maxn];
ll num[maxn];
ll pos[maxn];
int main() {
    cin>>n>>m;
    int cnt = 0;
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if(a[i]>a[j]){
				num[i]++;
			}
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(a[i]>a[j]){
				pos[i]++;
			}
		}
	}
	ll sum=0;
	for(int i=0;i<n;i++){
		sum+=pos[i];
	}
	
	sum%=mod;
	ll ssum = 0;
	ll temp = (m-1)*m/2;
	temp%=mod;
	temp*=sum;
	temp%=mod;
	ssum = temp;
	ll p = 0;
	for(int i=0;i<n;i++){
		p+=num[i];
	}
	p%=mod;
	p*=m;
	p%=mod;
	ssum+=p;
	ssum%=mod;
	cout<<ssum<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
int main() {
    int n,k;
    cin>>n>>k;
    ll sum=0;
    ll maxsum=0;
    vector<int> p(n);
    rep(i,n){
        cin>>p[i];
    }
    rep(i,k){
        sum+=p[i];
    }
    maxsum=sum;
    for(int i=k;i<n;i++){
        sum=sum-p[i-k]+p[i];
        maxsum=max(maxsum,sum);
    }
  cout<<fixed;
    cout<<setprecision(6)<<(maxsum+k)/2.0<<endl;
}


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

using namespace std;

#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long int
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define vii vector<pii>
#define pb push_back
#define B begin()
#define E end()
#define F first
#define S second
#define loop(z, v) for(auto &z: v)
#define nl "\n"
#define fat 1000000007

int main()
{
    boost
    vi a = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    int k;
    cin >> k;
    k--;
    cout << a[k] << nl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define r0 return 0;
#define f(k,i,n,j) for(ll k=i;k<=n;k=k+j)
#define cin(a) cin>>a;
#define loop while(t--)
#define vi vector<int>
#define vii vector<long long int>
#define SORT(v) sort(v.begin(),v.end());
#define mod (1e9+7)
#define crap ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
signed main()
{
    crap;
    string s;
    cin>>s;
    int a=0,b=0;
    for(int i=0;i<s.length();i++)
    {
        if(s[i]=='A')
        a++;
        else b++;
    }
    if(a==3 || b==3)
    cout<<"No"<<endl;
    else
    cout<<"Yes"<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,K;
  cin >> N >> K;
  string S;
  cin >> S;

  vector<int> nums;
  if (S.at(0) == '0') nums.push_back(0);
  for (int i = 0; i < S.size();) {
    int j = i;
    while (j < S.size() && S.at(j) == S.at(i)) j++;
    nums.push_back(j - i);  // 違うポイント
    i = j;
  }
  if (S.back() == '0') nums.push_back(0);
  // 累積和
  vector<int> sums((int)nums.size() + 1, 0);
  for (int i = 0;i < nums.size(); i++) sums.at(i+1) = sums.at(i) + nums.at(i);
  
  int res = 0;
  for (int left = 0; left < sums.size(); left += 2) {
    int right = left + K*2+1;
    if (right >= sums.size()) right = (int)sums.size()-1;
    res = max(res,sums.at(right) - sums.at(left));  // max関数ってこんな使い方できるんや
  }
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 1272
#include <iostream>
#include <cmath>
#include <iomanip>
#include <limits>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <list>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i=0;i<(n);i++)

int main(){
    ll n,ans=0;
    cin >> n;
    string a,b,c;
    cin >> a >> b >> c;
    rep(i,n){
        if(a[i] == b[i] && b[i] == c[i]){}
        else if(a[i] != b[i] && b[i] != c[i] && c[i] != a[i]) ans+=2;
        else ans+=1;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define fio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define pb push_back
#define mod 1000000007
#define vi vector<int>
#define si set<int>
#define pi pair<int,int>
#define li list<int>
#define fi first
#define in insert
#define se second
#define fr(i,n) for(i = 0 ; i < n ; i++)
int dp[100000];
int h[100000];
int solve(int k)
{
    if(dp[k-1]!=-1)
        return dp[k-1];
    for(int i = 3;i<k;i++)
    dp[i] = min(abs(h[i]-h[i-1])+dp[i-1],abs(h[i]-h[i-2])+dp[i-2]);

    return dp[k-1];

}
int main()
{
    fio
    int n,i,j,k;
    cin>>n;
    fr(i,n)
    cin>>h[i];
    dp[0]=0;
    dp[1]=abs(h[1]-h[0]);
    dp[2]=abs(h[2]-h[0]);
    for(i=3;i<n;i++)
        dp[i] = -1;
    cout<<solve(n);
    return 0;
}


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

using namespace std;
typedef long long ll;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int h1, m1, h2, m2, k;
    cin >> h1 >> m1 >> h2 >> m2 >> k;
    int ans = 0;
    while (h1 != h2 || m1 != m2) {
        ++ans;
        m1 = (m1 + 1) % 60;
        if (m1 == 0) ++h1;
    }
    ans = max(0, ans - k);
    cout << ans << '\n';
}

Measured memory_bytes: 3636
#include<ctime>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath> 
#include<cstring> 
#include<cassert>
#include<string>
#include<sstream>
#include<fstream>
#include<deque>
#include<queue>
#include<vector>
#include<map>
#include<list>
#include<stack>
#include<set>
#include<bitset>
#include<iomanip>
#include<utility>
#include<functional>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<complex>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cwchar>
#include<cwctype>
#include<exception>
#include<locale>
#include<numeric>
#include<new>
#include<stdexcept>
#include<limits>
using namespace std;

#define ll long long
#define INF 1e9
#define rep(i,n) for(int (i)=0;(i)<n;i++)
#define REP(i,n) for(int (i)=1;(i)<=n;i++)
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
inline void Fail(){
	printf("0");
	exit(0);
}

const int maxn=500005;
int n,ans;
char c[maxn];
string s;
int dp[maxn],pre[maxn];

int main(){
	scanf("%d%s",&n,c);
	s=c;
	pre[0]=s[0]=='1';
	REP(i,n-1){
		if(s[i]=='0')pre[i]=0;
		else pre[i]=pre[i-1]+1;
//		cout<<pre[i]<<endl;
	}
	dp[0]=0;
	REP(i,n-1){
		if(i<2)continue;
		dp[i]=dp[i-1];
		if(s[i-1]=='0'&&s[i]=='1'){
			for(int j=i-2;j>=0;j--){
				if(s[j]=='0')break;
				dp[i]=max(dp[i],(!j?0:dp[j-1])+i-2-(j-1));
			}
		}
		if(pre[i]&&i-pre[i]>=1&&s[i-pre[i]]=='0'&&s[i-pre[i]-1]=='1')
		dp[i]=max(dp[i],(i-pre[i]-2<0?0:dp[i-pre[i]-2])+pre[i]); 
		ans=max(ans,dp[i]);
//		cout<<dp[i]<<endl;
	}
	printf("%d",ans);
	return 0;
}

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

int main(void)
{
  int n;
  cin >> n;
  double result=0, count=0;
  for (int i=1; i<=n; ++i) {
    if (i % 2 != 0) {
      count++;
    }
  }
  result = count / n;
  cout << result << endl;
  return 0;
}


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

using namespace std;

int main() {
	vector<int> input;
	for(int i=0;i<3;i++) {
		int temp;
		cin >> temp;
		input.push_back(temp);
	}
	sort(input.begin(), input.end());
	for(int i=0;i<3;i++) {
		cout << input[i] << " \n"[i==2];
	}
	return 0;
}

Measured memory_bytes: 3164
#include <bits/stdc++.h>
#define REP(i,n)   for(int i=0;i<(n);++i)
#define FOR(i,a,b) for(long long i=(a);((a)<(b)?i<=(b):i>=(b));((a)<(b)?++i:--i))
#define ALL(v)     (v).begin(),(v).end()
#define debug(x)   cerr<<#x<<": "<<(x)<<endl
using namespace std;
using llong = long long;
using vi    = vector<int>;
using vvi   = vector<vi >;
using vvvi  = vector<vvi >;
using pii   = pair<int,int>;
constexpr int    INF=1e9;
constexpr double EPS=1e-9;
constexpr int    MOD=1e9+7;
template<class Type>
void line(const Type &a){int cnt=0;for(const auto &elem:a){cerr<<(cnt++?' ':'>');cerr<<elem;}cerr<<endl;}

int main(){//Refering other editorials.
	int n;
	cin>>n;
	
	vi l(n);
	REP(i,n) cin>>l[i];
	
	int ans=0;
	FOR(i,0,n-3)FOR(j,i+1,n-2)FOR(k,j+1,n-1){
		if(l[i]==l[j] or l[j]==l[k] or l[k]==l[i]){}
		else{
			if(abs(l[i]-l[j])<l[k] and l[k]<l[i]+l[j]) ans++;
		}
	}
	
	cout<<ans<<endl;
}

Measured memory_bytes: 3632
#include <stdio.h>
int main()
{
    int a[1002],i,j,k=0,n;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    scanf("%d",&a[i]);
    for(i=0;i<n;i++)
    {
        if(a[i])
        {
            k++;
           for(j=i+1;j<n;j++)
           {
            if(a[i]==a[j])
            {
                a[j]=0;
            }
           }
        }
    }
    printf("%d\n",k);
        return 0;
}

Measured memory_bytes: 128
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int64 {
	sc.Scan()
	i, e := strconv.ParseInt(sc.Text(), 10, 64)
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	sc.Split(bufio.ScanWords)
	a := nextInt()
	fmt.Println(a + a*a + a*a*a)
}


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

int main() {
int N, M;
  
    
    cin >> N>>M;
  int D = 2*M;
    vector<int> A(D), Sum(N);
    for(int i=0; i < D; i++){
        cin >>A.at(i);
    }
    for(int i=0; i < D ;i++){
      for(int j =0; j <N; j++){
        if(A.at(i) == j+1){
          Sum.at(j) ++ ;
      }
      }
    }
    for(int i=0; i < N ;i++)
    cout << Sum.at(i)<<endl;
}


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


int main(){
  int x; cin >> x;
  int y500 = 0;
  int y5   = 0;
  y500 = x / 500;
  x %= 500;
  y5 = x / 5;
  int ans = y500 *1000 + y5 * 5;
  cout << ans << endl;
}

Measured memory_bytes: 256