akhauriyash/Code-Regression huggingface dataset:
# ARC097D - Equals (ABC097D)
import sys
input = sys.stdin.readline


class UnionFind:
    def __init__(self, N):
        self.parent = [i for i in range(N + 1)]
        self.rank = [0] * (N + 1)

    def find(self, x):  # find the group (root) of a vertex
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def is_same(self, x, y):  # check two vertices are in the same group
        return self.find(x) == self.find(y)

    def unite(self, x, y):  # unite two groups
        x, y = self.find(x), self.find(y)
        if x == y:  # the same group
            return
        # unite a small one to a bigger one to balance trees
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


def main():
    # check i and Pi are connected components or not
    N, M = tuple(map(int, input().split()))
    P = tuple(map(int, input().split()))
    E = tuple(tuple(map(int, input().split())) for _ in range(M))
    U = UnionFind(N)  # construct a Union-Find tree (1-idx)
    for v, u in E:  # connected components are in the same group
        U.unite(v, u)
    ans = sum(U.is_same(i, p) for i, p in enumerate(P, 1))
    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 25184
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double lf;
typedef pair<int,int> ii;
typedef pair<ii,int> iii;
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define RREP(i,n) for (int i=n-1;i>=0;i--)
#define RST(i,n) memset(i,n,sizeof i)
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(),a.end()
#define X first
#define Y second
#define mkp make_pair
#define pb push_back
#define eb emplace_back
#define pob pop_back
#ifdef cold66
#define debug(...) do{\
    fprintf(stderr,"%s - %d (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
    _do(__VA_ARGS__);\
}while(0)
template<typename T>void _do(T &&_x){cerr<<_x<<endl;}
template<typename T,typename ...S> void _do(T &&_x,S &&..._t){cerr<<_x<<", ";_do(_t...);}
template<typename _a,typename _b> ostream& operator << (ostream &_s,const pair<_a,_b> &_p){return _s<<"("<<_p.X<<","<<_p.Y<<")";}
template<typename It> ostream& _OUTC(ostream &_s,It _ita,It _itb)
{
    _s<<"{";
    for(It _it=_ita;_it!=_itb;_it++)
    {
        _s<<(_it==_ita?"":",")<<*_it;
    }
    _s<<"}";
    return _s;
}
template<typename _a> ostream &operator << (ostream &_s,vector<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,set<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a,typename _b> ostream &operator << (ostream &_s,map<_a,_b> &_c){return _OUTC(_s,ALL(_c));}
template<typename _t> void pary(_t _a,_t _b){_OUTC(cerr,_a,_b);cerr<<endl;}
#define IOS()
#else
#define debug(...)
#define pary(...)
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#endif // cold66
//}
template<class T> inline bool chkmax(T &a, const T &b) { return b > a ? a = b, true : false; }
template<class T> inline bool chkmin(T &a, const T &b) { return b < a ? a = b, true : false; }
template<class T> using MaxHeap = priority_queue<T>;
template<class T> using MinHeap = priority_queue<T, vector<T>, greater<T>>;

const ll MAXn=1e5+5,MAXlg=__lg(MAXn)+2;
const ll MOD=1000000007;
const ll INF=0x3f3f3f3f;

set<int> st[31];
int main(){
    IOS();
    int n;
    cin >> n;
    string s;
    cin >> s;
    REP (i,n) {
        int cur = s[i] - 'a';
        st[cur].insert(i);
    }

    int q;
    cin >> q;
    while (q--) {
        int cmd;
        cin >> cmd;
        if (cmd == 1) {
            int x;
            char c;
            cin >> x >> c;
            x--;
            st[s[x]-'a'].erase(x);
            s[x] = c;
            st[c-'a'].insert(x);
        }
        else {
            int l,r;
            cin >> l >> r;
            l--, r--;
            int cnt = 0;
            REP (i,26) {
                auto it = st[i].lower_bound(l);
                if (it != st[i].end() && *it <= r) cnt++;
            }
            cout << cnt << endl;
        }
    }
}


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

using ll = long long;
#define ld long double
#define ull unsigned long long int

#define rep(i, n) for (int i = 0; i < (int)(n); i++)  // (i, 10) i=0～i=9まで
#define repr(i, n) for (int i = n; i >= 0; i--)   // (i, 10) i=10～i=0まで
#define FOR(i, m, n) for (int i = m; i < n; i++)  // (i, 3, 10) i=3～i=9まで
#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define pb push_back
#define ret return

typedef pair<int, int>    pii;
typedef vector<int>       vi;
typedef vector<vi>        vii;
typedef vector<long long> vl;

// 総数を1000000007で割った余り
const long long mod = 1e9 + 7;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

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

    // 入力
    int n;
    cin >> n;
    int num = sqrt(n);
    num *= num;

    // 処理
    cout << num << endl;

    // 出力

    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int h, w;
	cin >> h >> w;
	map<char, int> mp;
	rep(i,h)rep(j,w){
		char c;
		cin >> c;
		++mp[c];
	}
	int four = (h/2) * (w/2);
	int two = (h*w - four * 4) / 2;
	int f = 0, t = 0;
	for(auto p : mp){
		f += p.second / 4;
		p.second %= 4;
		t += p.second / 2;
	}
	if(f < four){
		cout << "No" << endl;
		return 0;
	}
	t += (f - four) * 2;
	if(t < two) cout << "No" << endl;
	else cout << "Yes" << endl;
	return 0;
}


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

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define MOD 1000000007LL

#define rep(i, n) for(ll (i) = 0LL;(i) < (ll)(n);(i)++)
#define rep2(i, s, e) for(ll (i) = (ll)(s);(i) < (ll)(e);(i)++)
#define repi(i, n) for(ll (i) = 0LL;(i) <= (ll)(n);(i)++)
#define repi2(i, s, e) for(ll (i) = (ll)(s);(i) <= (ll)(e);(i)++)
#define per(i, n) for(ll (i) = (ll)(n) - 1LL;(i) >= 0LL;(i)--)
#define per2(i, s, e) for(ll (i) = (ll)(s) - 1LL;(i) >= (ll)(e);(i)--)
#define peri(i, n) for(ll (i) = (ll)(n);(i) >= 0LL;(i)--)
#define peri2(i, s, e) for(ll (i) = (ll)(s);(i) >= (ll)(e);(i)--)
#define iter(i, it) for(auto &(i): (it))

template<typename T, typename U> ostream& operator<<(ostream &s, const pair<T, U> m) {
    cout << "(" << m.first << ", " << m.second << ")";
    return s;
}
template<typename T, typename U> ostream& operator<<(ostream &s, const map<T, U> m) {
    ll c = 0;
    cout << "{ ";
    iter(i, m) cout << i << (c++ == m.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const vector<T> &v) {
    cout << "{ ";
    rep(i, v.size()) cout << v[i] << (i == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const list<T> &v) {
    ll c = 0;
    cout << "{ ";
    iter(i, v) cout << i << (c++ == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}

int main(void) {
    vector<string> A{"SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"};
    string S;
    cin >> S;
    auto iter = find(A.begin(), A.end(), S);
    cout << 7 - distance(A.begin(), iter) << endl;
    return 0;
}


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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
#define rep(pos, len) for(int pos=0;pos<len;pos++)
#define repp(pos, len) for(int pos=1;pos<=len;pos++)
 
#define INF 987654321
#define IINF 2987654321987654321
#define MOD 1000000007


int main() {
	int n, k;
	scanf("%d%d", &n, &k);
	vector<ll> h(n, 0);
	for(int i = 0; i < n; i++)
		scanf("%lld", &h[i]);
	sort(h.begin(), h.end());
	ll sum = 0;
	for(int i = 0; i < n-k; i++)
		sum += h[i];
	printf("%lld", sum);
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define int long long int
#define MAXN 1000000007
#define endl '\n'
using namespace std;

void solve(){
    int n; cin >> n;
    set<string> s;

    for(int i = 0; i < n ; ++i){
        string str;
        cin >> str;
        s.insert(str);
    }

    cout << s.size();
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    solve();

    return 0;
}

Measured memory_bytes: 19248
f=0
while 1:
    try:n=int(input())
    except:break
    if f:print()
    f=1
    a=[['*' for _ in range(5)]for _ in range(8)]
    for i in range(4,-1,-1):
        b=n%10
        a[not b//5][i]=' '
        a[b%5+3][i]=' '
        n//=10
    a[2]='='*5
    for i in a:
        print(''.join(i),end='')
        print()

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

void solve(){
  string s; cin >> s;
  vector<int> v(26, 0);
  int n = s.size();
  for(int i = 0; i < n; i++){
    v[s[i] - 'a']++;
  }
  for(int i = 0; i < 26; i++){
    if(v[i] == 0){
      cout << (char)(i + 'a') << endl;
      return;
    }
  }
  cout << "None" << endl;
  return;
}

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


Measured memory_bytes: 512
/* WORK HARD MAN ! IT DEFINETELY AIN'T EASY FOR THE PRIZE IT HOLDS .... */
/* GET YOUR ASS TO WORK ALREADY */
/* FALTU HI LIKH ... BUT KHALI NI BAITHNA */
#include<bits/stdc++.h>

#define fast ios_base::sync_with_stdio(false); cin.tie(nullptr); cin.tie(nullptr);
#define int long long
#define pb emplace_back
#define range(v) v.begin(),v.end()
#define mod 1000000007
#define inf 1e15
#define pii pair<int,int>
#define ff first
#define ss second
// #define N --

using namespace std;

int n;
vector<vector<int>> a;
vector<vector<int>> dp;

int vacation(int i = 0, int ld = 4) {
	if (i == n) return 0;
	if (dp[i][ld] != -1) return dp[i][ld];

	int ans = -inf;
	for (int j = 0; j < 3; j++)
		if (ld != j)
			ans = max(ans, vacation(i + 1, j) + a[i][j]);


	return dp[i][ld] = ans;

}

/* if not able to handle the ques.. see up */
int32_t main() {
	fast
	int t_c = 1;
//	cin >> t_c;
	while (t_c--) {
		cin >> n;
		a.resize(n, vector<int>(3));
		dp.resize(n, vector<int>(5, -1));
		for (vector<int> &v : a)
			for (int &i : v)
				cin >> i;
		cout << vacation() << endl;
	}
}

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

using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define MIN(a,b) ((a)>(b)? (b): (a))
#define MAX(a,b) ((a)<(b)? (b): (a))

const long long INF = 1LL << 60;
typedef unsigned long long ll;
const long long MOD = 1000000000 + 7;

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int cnt_w = 0;
    int out = 0;
    rep(i, n) {
        if (s[i]=='W') cnt_w++;
    }
    for (int i = n-1; i >= n-cnt_w; i--) {
        if (s[i]=='R') out++;
    }
    cout << out << endl;
    return 0;
}

Measured memory_bytes: 3748
n,k,*a=map(int,open(0).read().split())
now=1
if k<=n:
  for i in range(k):
    now=a[now-1]
  print(now)
  exit()
# 絶対ループする
visited=[False]*n
visited[now-1]=-1
for i in range(4*10**5):
  now=a[now-1]
  if visited[now-1]==False:
    visited[now-1]=i
  else:
    c,d=visited[now-1],i
    break

k=(k-c)%(d-c)+c
while k<n:
  k+=(d-c)
now=1
for i in range(k):
  now=a[now-1]
print(now)

Measured memory_bytes: 96728
#include <iostream>
#include <cstdio>
#include <bitset>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <utility>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;
using ll=long long;
using vint=vector<int>;
using pint=pair<int,int>;

const double EPS = 1e-9;

#define rep(i,n) for(int i=0;i<int(n);++i)
#define REP(i,a,b) for(int i=int(a);i<int(b);++i)
#define SHOW(a) cout << #a << " = " << a << endl;

void solve(){
	string a, b;
	cin >> a >> b;
	sort(a.begin(), a.end());
	sort(b.rbegin(), b.rend());
	if(a < b){
		cout << "Yes";
	}else{
		cout << "No";
	}
	cout << endl;
}

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

Measured memory_bytes: 256
import java.util.*;
 
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int S = sc.nextInt();
		int W = sc.nextInt();

		if(W >= S)
		System.out.println("unsafe");
		else
		System.out.println("safe");
	}
}

Measured memory_bytes: 35400
#include <iostream>
#include <vector>
#include <map>

int main() {
    int N; std::cin >> N;
    std::vector<int> a(N, 0);
    std::map<int, long long> c;
    for (int i = 0; i < N; i++) {
        std::cin >> a[i];
        c[a[i]]++;
    }

    std::vector<long long> d(N+1, -1);
    for (int i = 0; i < N; i++) {
        if (d[c[a[i]]] < 0) {
            long long s = 0;
            c[a[i]]--;
            for (const auto cc: c) {
                s += cc.second * (cc.second-1) / 2;
            }
            c[a[i]]++;
            d[c[a[i]]] = s;
        }
        std::cout << d[c[a[i]]] << std::endl;
    }
    return 0;
}


Measured memory_bytes: 11904
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#include <algorithm>
#include <array>
#include <iostream>
#include <string>
#include <vector>

int main(void) {
  int N;
  scanf("%d", &N);
  std::vector<std::string> W;

  for (int i = 0; i < N; i++) {
    std::string str;
    std::cin >> str;
    std::vector<std::string>::iterator result = std::find(W.begin(), W.end(), str);
    if (i == 0 ||
        (result == W.end() && W.back().back() == str.front())) {
      W.push_back(str);
    } else {
      puts("No"); return 0;
    }
  }
  puts("Yes"); return 0;
}

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

int main(){
  int n,x;
  cin >> n >> x;
  vector<int> L(n);
  for(int i = 0; i < n; i++){
    cin >> L[i];
  }
  int ans = 1;
  vector<int> D(n+1);
  D[0] = 0;
  for(int i = 1; i < n+1; i++){
    D[i] = D[i-1] + L[i-1];
    if(D[i] <= x){
      ans++;
    }
  }
  cout << ans << endl;
  }

Measured memory_bytes: 256
#include<stdio.h>
int main(void){
	int x,y,z,a;
	
	scanf("%d %d %d",&x,&y,&z);
	if(x>z){
		a=x;
		x=z;
		z=a;
	}
	if(x>y){
		a=x;
		x=y;
		y=a;
	}
	if(y>z){
		a=y;
		y=z;
		z=a;
	}
	printf("%d %d %d\n",x,y,z);
	return 0;
}

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

int main(){
  	bool judge = true;
    while(judge){
    	int H,W;
    	cin >> H >> W ;
    	if ( H == 0 && W == 0) {
      		judge = false;
    	}
    	else{
        	for ( int i = 0 ; i < H ; i++ ){
            	for ( int j = 0 ; j < W ; j++ ){
                	cout << "#";
            	} 
            	cout << endl;
        	}
    	cout << endl;
    	}
	}
}


Measured memory_bytes: 3088
N = gets.to_i
S = []
N.times do 
  S << gets.to_i
end

T = S.inject(:+)
ND = S.select{|x| x % 10 != 0}

if ND.size == 0
  puts 0
elsif T % 10 != 0
  puts T
else
  puts T - ND.min
end

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

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

  if (A >= K)
  {
    cout << A - K << " " << B << endl;
  }
  else if (A + B >= K)
  {
    cout << 0 << " " << B - (K - A) << endl;
  }
  else
  {
    cout << 0 << " " << 0 << endl;
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>
using namespace std;
int main(void){
    // Your code here!
    int H,W,i,j,n;
    while(1){
        cin>>H>>W;
        if(H==0&&W==0){
            break;
        }
        for(i=0;i<H;i++){
            for(j=0;j<W;j++){
                cout<<"#";
            }
            cout<<endl;
        }
        cout<<endl;
        
    }
    
    return 0;
}


Measured memory_bytes: 3068
// Problem : C - Peaks
// Contest : AtCoder - AtCoder Beginner Contest 166
// URL : https://atcoder.jp/contests/abc166/tasks/abc166_c
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)
#include<bits/stdc++.h>
using namespace std;
#define fastIO std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0)
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
//#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
//mt19937 mrand(random_device{}()); 
//int rnd(int x) { return mrand() % x;}
const ll mod=1000000007;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

const int maxn = 1e5 + 10; 

int n,m;
int h[maxn],vis[maxn];
vector<int>g[maxn];

int main()
{
	fastIO;
	cin >> n >> m;
	rep(i,1,n + 1) cin >> h[i];
	rep(i,0,m){
		int u,v;
		cin >> u >> v;
		g[u].pb(v);
		g[v].pb(u);
	}	
	int ans = 0;
	rep(i,1,n + 1) {
		if(vis[i]) continue;
		int suc = 1;
		for(int j = 0; j <(int)g[i].size(); ++j) {
			int v = g[i][j];
			if(h[i] <= h[v]) {
				suc = 0;
				//break;
			}
			else vis[v] = 1;
		}
		if(suc) ans++;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 9576
import math
from collections import defaultdict
N = int(input())
d = defaultdict(int)
tmp = N
for i in range(2, int(math.sqrt(N))+1):
    while tmp % i == 0:
        d[i] += 1
        tmp /= i

if tmp > 1:
    d[tmp] += 1
ans = 0
for key, value in d.items():
    i = value
    j = 1
    while value >= j:
       ans += 1
       value -= j
       j += 1
print(ans)

Measured memory_bytes: 68480
import heapq
t = 1
def max(a,b):
	if a > b:
		return a
	return b
while t > 0:
	t -= 1
	# n = map(int,input().split())
	n = int(input())
	# a = list(map(int,input().strip().split()))[0:n]
	# b = list(map(int,input().strip().split()))[0:n]
	c = list(map(int,input().strip().split()))[0:n-1]
	b = []
	for i in range(n):
		b.append(0)
	b[0] = c[0]
	b[n-1] = c[n-2]
	for i in range(1,n-1):
		b[i] = min(c[i],c[i-1])
	ans = 0
	for i in range(n):
		ans += b[i]
	print(ans)
	# print(n*n*n)
	# m = 1000
	# i = 0
	# while i < n:
	# 	j = i
	# 	while j+1 < n and v[j+1] >= v[j]:
	# 		j += 1
	# 	x = m//v[i]
	# 	m = m%v[i]
	# 	temp = x*v[j]
	# 	m += temp
	# 	i = j+1
	# print(m)


Measured memory_bytes: 62380
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<unordered_map>
#include<array>
#include<map>
#include<iomanip>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
#define dme cout<<-1<<endl;return 0
//ios::sync_with_stdio(false);
//<< setprecision(5)
const int mod=1000000007;
const int big=1e9+10;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-7;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){return a/gcd(a,b)*b;}
int main(void){
	ios::sync_with_stdio(false);
	int n,K,i;cin>>n>>K;
	llint ans=0;
	vector<pair<int,llint>> a(n);
	for(i=0;i<n;i++){cin>>a[i].fir>>a[i].sec;}
	for(int h=0;h<=30;h++){
		int ink=K;
		if(h<30&&(K&(1<<h))==0){continue;}
		if(h<30){
			ink^=(1<<h);
			ink|=(1<<h)-1;
		}
		//inkについて調べる
		llint gen=0;
		for(i=0;i<n;i++){
			if((ink|a[i].fir)==ink){gen+=a[i].sec;}
		}
		maxeq(ans,gen);
	}
	cout<<ans<<endl;
	return 0;
}

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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

template<typename T> struct Sum2 {
	typedef vector<vector<T>> A;
	A s;
	int X, Y;
	
	Sum2() { X = Y = -1; }
	Sum2(A & p) { init(p); }
	void init(A & p) {
		X = p.size();
		Y = p[0].size();
		s = A(X + 1, vector<T>(Y + 1, 0));
		
		inc1(x, X) {
		inc1(y, Y) {
			s[x][y] = p[x - 1][y - 1];
		}
		}
		inc1(x, X) {
		inc1(y, Y) {
			s[x][y] += s[x - 1][y];
		}
		}
		inc1(x, X) {
		inc1(y, Y) {
			s[x][y] += s[x][y - 1];
		}
		}
	}
	T sum(int xl, int xh, int yl, int yh) { // [xl, xh) × [yl, yh)
		assert(inII(xl, 0, X));
		assert(inII(xh, 0, X));
		assert(inII(yl, 0, Y));
		assert(inII(yh, 0, Y));
		assert(xl <= xh);
		assert(yl <= yh);
		return s[xh][yh] - s[xh][yl] - s[xl][yh] + s[xl][yl];
	}
};

#define UQ(v) (v.erase(unique(ALL(v)), v.end()) - v.begin())

LL n, k, x[50], y[50];
vector<vector<int>> p(50, vector<int>(50, 0));
vector<LL> vx, vy;
map<LL, LL> mx, my;

int main() {
	cin >> n >> k;
	inc(i, n) { cin >> x[i] >> y[i]; }
	
	inc(i, n) {
		vx.PB(x[i]);
		vy.PB(y[i]);
	}
	
	sort(ALL(vx));
	sort(ALL(vy));
	int xx = UQ(vx);
	int yy = UQ(vy);
	inc(i, xx) { mx[vx[i]] = i; }
	inc(i, yy) { my[vy[i]] = i; }
	
	inc(i, n) { p[mx[x[i]]][my[y[i]]]++; }
	
	
	Sum2<int> s(p);
	
	LL ans = 4e18;
	inc(xh, xx) {
	inc(xl, xh) {
	inc(yh, yy) {
	inc(yl, yh) {
		int c = s.sum(xl, xh + 1, yl, yh + 1);
		LL v = (vx[xh] - vx[xl]) * (vy[yh] - vy[yl]);
		if(c >= k) { setmin(ans, v); }
	}
	}
	}
	}
	
	cout << ans << endl;
	
	return 0;
}


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

#define ll               long long
#define inf            1e18
#define w(x)          int x; cin>>x; while(x--)
#define endl          "\n"
#define boostUP   ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define fsr(i,n)      for(int i=0;i<n;i++)
#define fcr(i,a,b)   for(int i=a;i<b;i++)
#define pb             push_back
#define sz(arr)      sizeof(arr)/sizeof(arr[0])




int main(void)
{
    boostUP;

    int arr[5];
    int sum = 0;
    for(int i = 0; i < 5; i++)
    {
        cin >> arr[i];
        sum += arr[i];

    }
    cout << 15 - sum <<endl;




    return 0;

}



Measured memory_bytes: 3632
#include <stdio.h>
#include <string.h>
#define mod 1000000007
typedef long long ll;

int main(void) {
  ll i, j, k, n, ans, cnt = 1;
  char s[100010];
  scanf("%s", s);
  n = strlen(s);
  ll p3[n + 1], p2[n + 1];
  p3[0] = p2[0] = 1;
  for(i = 0; i < n; ++i) p3[i + 1] = (p3[i] * 3) % mod, p2[i + 1] = (p2[i] * 2) % mod;
  ans = p3[n - 1];
  for(i = 1; i < n; ++i) if(s[i] == '1') {
    ans += p3[n - i - 1] * p2[cnt];
    ans %= mod;
    cnt++;
  }
  ans += p2[cnt];
  ans %= mod;
  printf("%lld", ans);
  return 0;
}

Measured memory_bytes: 1792
import java.util.*;
class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String str = sc.next();
		System.out.print(str.charAt(0));
		System.out.print(str.length()-2);
		System.out.print(str.charAt(str.length()-1)+"\n");
	}
}

Measured memory_bytes: 21972
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> g(10);
vector<bool> visited(10,false);
int ans = 0;
void dfs(int x, int depth, int n){
    if(depth == n) {
        ans++;
        return;
    }
    visited[x] = true;
    for(int nv:g[x]){
        if(visited[nv]) continue;
        dfs(nv,depth+1,n);
        visited[nv] = false;
    }
    return;
}
int main(){
    int n,m;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a,b;
        cin >> a >> b;
        a--; b--; 
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(0,1,n);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3612
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;

ll Max = 1000000000000000000;

int main() {
	int n;
	cin >> n;
	ll ans = 1;
	ll a[n];
	for(int i = 0; i < n; i++){
		cin >> a[i];
	}
	for(int i = 0; i < n; i++){
		if(a[i] == 0){
			cout << 0;
			return 0;
		}
	}
	for(int i = 0; i < n; i ++){
		if(a[i] <= (Max / ans)){
			ans *= a[i];
		}
		else{
			cout << -1;
			return 0;
		}
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 4392
#pragma GCC optimize ("-O3")
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
//#include <boost/multiprecision/cpp_int.hpp>
//using namespace boost::multiprecision;
using namespace std;

#define all(c) (c).begin(),(c).end()
#define endl "\n"
#define ff first
#define ss second
#define allr(c) (c).rbegin(),(c).rend()
#define ifr(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define pof pop_front
#define pob pop_back
#define pb emplace_back
#define pf emplace_front
#define fstm(m,n,r) m.reserve(n);m.max_load_factor(r)
#define mp make_pair
#define mt make_tuple
#define inf LLONG_MAX
#define os tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
//order_of_key (k) : Number of items strictly smaller than k .
//find_by_order(k) : K-th element in a set (counting from zero).
const double PI = acos(-1);
typedef complex<double> cd;
typedef long long ll;
ll gcd(){return 0ll;} template<typename T,typename... Args> T gcd(T a,Args... args) { return __gcd(a,(__typeof(a))gcd(args...)); }
typedef map<ll,ll> mll;
typedef map<string,ll> msll;
typedef unordered_map<ll,ll> umap;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
typedef long double ld;
#define mod 1000000007 
#define N 100001

struct tt {
    int siz;
    ll mat[51][51];
    tt(int s) {
        siz=s;
        ifr(i,0,51) ifr(j,0,51) mat[i][j]=0;
    }
    int size() {
        return siz;
    }
};

tt operator*(tt x,tt y) {
    tt res(x.size());
    ifr(i,0,res.size()) ifr(j,0,res.size()) ifr(k,0,res.size()) {
        res.mat[i][j]+=(x.mat[i][k]*y.mat[k][j])%mod;
        res.mat[i][j]%=mod;
    }
    return res;
}

tt power(tt a,ll b) {
    tt res(a.size());
    ifr(i,0,a.size()) res.mat[i][i]=1;
    while(b) {
        if(b&1) res=(res*a);
        b>>=1;
        a=a*a;
    }
    return res;
}

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

    int n;ll k;
    cin>>n>>k;
    tt a(n);
    ifr(i,0,n) ifr(j,0,n) cin>>a.mat[i][j];
    a = power(a,k);
    ll sum=0;
    ifr(i,0,n) ifr(j,0,n) sum=(sum+a.mat[i][j])%mod;
    cout<<sum<<endl;
    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define ALL(obj) begin(obj), end(obj)
#define debug(x) cerr << #x << ": " << x << '\n'
using namespace std;
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}

using ll = long long;
using ull = unsigned long long;
const int INF = 1e9;
// const int MOD = 1e9 + 7;

int main() {
    int N;
    string S;
    cin >> N >> S;
    ll sum = 0;
    map<char, ll> m;
    vector<char> C = {'R',
                      'G',
                      'B'};
    for (int i = 0; i < N; i++) {
        ll tmp = 1;
        for (int j = 0; j < 3; j++) {
            if (S[i] != C[j]) { tmp *= m[C[j]]; }
        }
        sum += tmp;
        for (int j = 0; j < i; j++) {
            int k = j - (i - j);
            if (k >= 0) {
                if (S[k] != S[j] && S[j] != S[i] && S[i] != S[k]) {
                    sum--;
                }
            }
        }
        m[S[i]]++;
    }
    cout << sum << endl;
}


Measured memory_bytes: 3636
//問題URL
//https://beta.atcoder.jp/contests/abc079/tasks/abc079_d

//解き方メモ
//最短経路問題。ダイクストラ法を使用
    
#include<iostream>
#include<queue>
#include<utility>
#include<vector>
using namespace std;

int main(){
  int h,w;
  int c[10][10];
  int a[201][201];
  int cnt[10] = {0,0,0,0,0,0,0,0,0,0};
  int cost = 0;

  //入力（数字カウント含む）
  
  cin >> h >> w;
  for (int i = 0; i < 10; i++) {
    for (int j = 0; j < 10; j++) {
      cin >> c[i][j];
    }
  }

  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      cin >> a[i][j];
      
      //数字別の件数カウント
      if(a[i][j] != -1){
	cnt[ a[i][j] ]++;
      }
    }
  }

  
  //計算
  
  for (int i = 0; i < 10; i++) {
    //元の数字をスタート、１をゴールとする最短経路問題と考える
    //i=1はゴール済みなので考えない。出現しない数字（cnt==0）も考えない
    if(i!=1 && cnt[i]>0){
      //優先度付きキューを使用する
      //(コスト、現在位置）のpairを要素とする
      //コストが小さい順のキューとなるよう宣言
      priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
      q.push(make_pair(0,i)); //開始点をキューに入れる。コスト０
      while(true){
	//先頭（コスト最小）を取り出す
	pair<int,int> p = q.top();
	q.pop();

	if(p.second == 1){ //ゴールに到達した場合
	  cost += cnt[i] * p.first;
	  break;
	} else { //到達しなかった場合
	  for (int k = 0; k < 10; k++) {
	    if(k != p.second){ //移動しない場合は考えない。ループしてしまうため
	      q.push(make_pair(p.first+c[p.second][k],k));
	    }
	  }
	}
      }
    }
  }

  cout << cost << endl;
  
  return 0;
}


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

int main()
{
	for(int i = 1;i < 10;i++)
	{
		for(int m = 1;m < 10;m++)
		{
			std::cout << i << "x" << m << "=" << i*m << std::endl;
		}
	}
    return 0;
}

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

int digit_sum(int n)
{
    if (n < 10) return n;

    return n % 10 + digit_sum(n / 10);
}

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

    int sum = 0;
    int d_sum = 0;
    for (int i = 1; i <= N; i++)
    {
        d_sum = digit_sum(i);
        if (A <= d_sum && d_sum <= B)
        {
            sum += i;
        }
    }
    cout << sum << endl;
}


Measured memory_bytes: 3612
import java.util.*;
import java.lang.*;
import java.math.*;

public class Main {
	Scanner sc = new Scanner(System.in);

	class int2{
		double x;
		double y;
		int2(double x,double y){
			this.x = x;
			this.y = y;
		}
		double vec(int2 tar){
			return this.x*tar.y - this.y*tar.x;
		}
	}
	
	void run() {
		for (;;) {
			if (!sc.hasNextInt())
				break;
			int[] sim = new int[6];
			for(int i =0; i < 6 ; i++){
				sim[i] = sc.nextInt();
			}
			int2 x = new int2(sim[0],sim[3]);
			int2 y = new int2(sim[1],sim[4]);
			int2 u = new int2(sim[2],sim[5]);
			
			Double ansy = (x.vec(u)/ x.vec(y)); 
			Double ansx = (u.vec(y)/ x.vec(y)); 
			String outx = ansx.toString()+"00";
			String outy = ansy.toString()+"00";
			if(outx.equals("-0.000")){
				outx = outx.substring(1);
			}
			if(outy.equals("-0.000")){
				outy = outy.substring(1);
			}
			int indexx = outx.indexOf('.');
			int indexy = outy.indexOf('.');
			
			System.out.println(outx.substring(0,indexx+1) + outx.substring(indexx+1,indexx+4) +" "+ outy.substring(0,indexy+1) + outy.substring(indexy+1,indexy+4));		
		}

	}

	public static void main(String[] args) {
		Main m = new Main();
		m.run();

	}
}

Measured memory_bytes: 11000
#include<iostream>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
ll a[maxn], b[maxn], k, n, m, sum, p;
double c, r;
string s, t;


int main(){
    ios_base::sync_with_stdio(0);
    cin>>n;
    for(ll i = -1000; i <= 1000; i++){
        for(ll j = -1000; j <= 1000; j++){
            if((i*i*i*i*i - j*j*j*j*j) == n){
                cout<<i<<' '<<j<<endl;
                return 0;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 3588
#include <stdio.h>
#include <math.h>

typedef long long ll;

int main() {
	int n;
	scanf("%d", &n);
	// ans = 10^n - 2 * 9^n + 8^n
	ll p = 1e9 + 7;
	
	ll pow10 = 1, pow9 = 1, pow8 = 1;
	for (int i = 0; i < n; i++)
	{
		pow10 = (pow10 * 10) % p;
		pow9 = (pow9 * 9) % p;
		pow8 = (pow8 * 8) % p;
	}
	ll ans = pow10 - 2 * pow9 + pow8;
	ans += p * 4;
	ans %= p;
	printf("%lld", ans);
	return 0;
}


Measured memory_bytes: 1736
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

const int maxn = 100010 * 2;
const int INF = 1<<30;

vector<int> g[maxn];
int father[maxn];
int root = 1;
bool flg;
int dp[maxn];
int n;

void link(int u, int v)
{
	g[u].push_back(v);
	g[v].push_back(u);
}

bool check2(int r, vector<int> son, int B)
{
	son.erase(son.begin()+r);
	for (int i=0;i<son.size()/2;i++)
	{
		int j = son.size() - 1 - i;
		if (son[i] + son[j] > B) return false;
	}
	return true;
}

void dfs2(int u, int f, int B)
{
	vector<int> son; son.clear();
	for (int i=0;i<g[u].size();i++)
	{
		int v = g[u][i];
		if (v == f) continue;
		dfs2(v,u,B);
		son.push_back(dp[v]);
	}
	sort(son.begin(), son.end());
	int size = son.size();

	if (size == 0)
	{
		dp[u] = 1;
	}
	else if (size % 2 == 1) //u为偶度点
	{
		int lb = 0, ub = size-1; //[lb,ub]
		while (ub - lb >= 1)
		{
			int mid = (ub + lb)/2;
			if (check2(mid,son,B)) ub = mid;
			else lb = mid+1;
		}
		if (!check2(lb,son,B)) flg = false; //无论怎么样都满足不了要求
		dp[u] = son[lb] + 1;
		if (dp[u] > B && u != root) flg = false; 
	}
	else //u为奇度点
	{
		son.push_back(0); //如果选中0表示u作为新的起点，如果没有选中，表示有一个儿子是通过u出去的
		sort(son.begin(), son.end());
		int lb = 0, ub = size; //[lb,ub]
		while (ub - lb >= 1)
		{
			int mid = (ub + lb)/2;
			if (check2(mid,son,B)) ub = mid;
			else lb = mid+1;
		}
		dp[u] = son[lb] + 1;
		if (!check2(lb,son,B)) flg = false;
		if (dp[u] > B && u != root) flg = false; 
	}
}

bool check1(int B)
{
	for (int i=0;i<=n+10;i++) dp[i] = INF;
	flg = true;
	dfs2(root,0,B);
	//cout<<B<<" "<<flg<<" "<<dp[root]<<endl;
	if (flg == false || dp[root] > B+1) return false;
	else return true;
}

int main()
{
	//freopen("F.in","r",stdin);
	scanf("%d",&n);
	for (int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		link(u,v);
	}
	for (int i=1;i<=n;i++)
	{
		if (g[i].size() == 1)
		{
			root = i;
			break;
		}
	}

	int oddNum = 0;
	for (int i=1;i<=n;i++) oddNum += g[i].size() % 2;
	int A = oddNum / 2;

	int Blb = 0, Bub = n-1; //[Blb,Bub]
	while (Bub - Blb >= 1)
	{
		int mid = (Blb + Bub)/2;
		if (check1(mid)) Bub = mid;
		else Blb = mid+1;
	}

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



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

#define rep(i,n)  for(int i=0;i<n;++i)
#define sc1(a)  scanf("%d",&a)

int main(){
    bool f=0;
    int n;
    long long a,b=0ll,x=2e9;
    sc1(n);
    rep(i,n){
        scanf("%lld",&a);
        if (a<0) f=f^1;
        b+=abs(a);
        x=min(x,abs(a));
    }
    printf("%lld\n",f?b-x*2:b);
    return 0;
}


Measured memory_bytes: 3828
L, N = map(int, input().split())
X = [int(input()) for _ in range(N)]
Y = [L - X[N-i-1] for i in range(N)]

def clockwise(X, Y):
    cum_X = [0 for _ in range(N+1)]
    cum_Y = [0 for _ in range(N+1)]
    for i in range(1, N+1):
        cum_X[i] = X[i-1] + cum_X[i-1]
        cum_Y[i] = Y[i-1] + cum_Y[i-1]
    d = 0
    for i in range(N):
        x_last = (N-i-1) // 2
        y_last = N-i-1-x_last
        if (N-i) % 2 == 0:
            last = Y[y_last-1]
        else:
            last = X[i+x_last]
        d = max(d, 2*(X[i]+cum_X[i+x_last+1]-cum_X[i+1]+cum_Y[y_last])-last)
    return d

ans = max(clockwise(X, Y), clockwise(Y, X))
print(ans)


Measured memory_bytes: 40000
#include<iostream>
#include<string>

bool iscan[10];

int main(){
    std::string in;
    std::cin>>in;
    std::string str;
    for(int i=0;i<in.size();++i){
        if(in[i]=='B'&&!str.empty())
            str.pop_back();
        else if(in[i]!='B')
            str.push_back(in[i]);
    }
    std::cout<<str<<std::endl;
    return 0;
}

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

using namespace std;

int main()
{
	int n, w;
	cin >> n >> w;
	vector<pair<int, int>> v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i].first >> v[i].second;
	}

	vector<vector<long long>> dp(n + 1, vector<long long>(w + 1));
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= w; j++) {
			if (j - v[i - 1].first < 0) {
				dp[i][j] = dp[i - 1][j];
			}
			else {
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i - 1].first] + v[i - 1].second);
			}
		}
	}
	cout << dp[n][w] << endl;

	return 0;
}


Measured memory_bytes: 82980
#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, class T2> void amax(T& a,T2 b){ if(a < b) a = b;}


int main()
{
	cin.tie(0); ios_base::sync_with_stdio(false);
	int n;
	cin >>n;
	VI v(100100);
	rep(i,n){int z; cin >>z; v[z]++;}

	int ans = 0;
	rep2(i, 1, 100001){
		ans = max(ans, v[i-1]+v[i]+v[i+1]);
	}
	cout << ans <<"\n"; 
	return 0;
}


Measured memory_bytes: 640
MOD = 10 ** 9 + 7
N, K = map(int, input().split())
A = list(map(int, input().split()))

ans = 0
tmp = ((K * (K - 1))//2) % MOD

for i in range(N):
    before = 0
    after = 0
    for j in range(i):
        if A[i] > A[j]:
            before += 1
    for j in range(i + 1, N):
        if A[i] > A[j]:
            after += 1
    # print (i, before, after)
    ans += (tmp * (before + after) + after * K)
    ans %= MOD

print (ans)


Measured memory_bytes: 3188
#include<iostream>
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int k,s ;  
  cin >> k >> s;
  int count=0;
  for(int x=0;x<=k;++x){
    for(int y=0;y<=k;++y){
      int z=s-x-y;
      if(z<=k && z>=0)
        count++;
    }
  }
  cout << count << "\n";

    return 0;
}


Measured memory_bytes: 256
// :)
// "Khodaya, be man "Tagwaye setiz" biamooz ta
//  dar anbuh masuliat nalaghzam ..." -Shariati
#include <bits/stdc++.h>

using namespace std;
typedef long long int64;
typedef pair<int,int> pii;
typedef pair<int64,int64> pii64;

#define PB push_back
#define MP make_pair
#define F first
#define S second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

const int maxn = 1e5+7;
const int64 M = 1e9+7;
const int64 I = 1e9;

int N, A, B;

int main () {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	// 
	cin >> N >> A >> B;
	//
	cout << min(A, B) << " " << max(0, A + B - N) << "\n";
	//
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin>>N;
  vector<int> A(N);
  for(int i=0;i<N;i++){
    cin>>A.at(i);
  }
  int ans=0;
  sort(A.begin(),A.end());
  for(int i=0;i<N-1;i++){
    ans+=A.at(i+1)-A.at(i);
  }
  cout<<ans<<endl;
  return 0;
}

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

using namespace std;

int main(){
    
    string a, b;
    cin >> a >> b;
    string g(1, '+');
    b = b + g;
    int s = (int)a.size();

    int c = 0;
    while(c < s + 1){

        if(a[0] != b[c]){
            c++;
            continue;
        }else{
            for(int d = 0; d < s; d++){
                if(b[(c + d)%s] == a[d]){
                    if(d == s - 1){
                        cout << "Yes" << endl;
                        return 0;
                    }
                    continue;
                }else break;               
            }
        }
    c++;
    }
    cout << "No" << endl;
    return 0;
}

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

#define rep(X,N) for(ll X = 0LL; X < (N); X++)
#define PI (acos(-1.0))
#define MODN 1000000007
#define MODN2 998244353
#define ALL(V) (V).begin(),(V).end()
#define INT_MAX_HALF (INT_MAX / 2)
#define EPS (1e-10)

using namespace std;
typedef long long ll;

int main(){

    int n,k;
    cin >> n >> k;

    int ans = k;

    for(int i = 1; i < n; i++){
        ans *= (k - 1);
    }

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
# 累積話の考え方を使う
H, W, D = map(int, input().split())
status = {}
for i in range(H):
    A = list(map(int, input().split()))
    for j in range(W):
        status[A[j]] = (i+1, j+1)
Q = int(input())
query = [list(map(int, input().split())) for _ in range(Q)]
# print(status)

# 目的地は必ずDだけ小さいマスからしか移動してこない
cumulative_sum = [0] * (H*W+1)
for i in range(H*W+1):
    if i <= D:
        cumulative_sum[i] = 0
        continue
    else:
        cumulative_sum[i] = cumulative_sum[i-D] + abs(status[i][0] - status[i-D][0]) + abs(status[i][1] - status[i-D][1])

for s, t in query:
    print(cumulative_sum[t] - cumulative_sum[s])


Measured memory_bytes: 47340
import java.util.Scanner;


public class Main {
	public static void main(String[] args) {
		try(Scanner sc = new Scanner(System.in)){
			while(sc.hasNextInt()) {
				int x = sc.nextInt();
				int y = sc.nextInt();
				int s = sc.nextInt();
				if(x==0 && y==0 && s==0) break;
				
				int max=0;
				for(int i=1;i<s;i++) {
					for(int j=1;i+j<=s;j++) {
						if(i*(100+x)/100 + (j)*(100+x)/100 == s) {
							int sum =i*(100+y)/100 + (j)*(100+y)/100;
							if(sum>max) max=sum;
						}
					}
				}
				System.out.println(max);
			}
		}
	}
}




Measured memory_bytes: 29112
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAX_N = 200005;
typedef long long i64;

char S[MAX_N];
i64 g[105][26], len[MAX_N];

int N, T;

void work(i64 x, i64 *cnt) {
  memset(g, 0, sizeof g);
  
  int mx = 1;
  for (int i = 1; i <= N; ++i) g[1][S[i] - 'a']++;
  for (int i = 1; i <= T; ++i) g[0][S[i] - 'a']++;
  len[0] = T, len[1] = N;

  while (len[mx] < x) {
    ++mx;
    for (int i = 0; i < 26; ++i) g[mx][i] = g[mx - 1][i] + g[mx - 2][i];
    len[mx] = len[mx - 1] + len[mx - 2];
  }
  
  if (N % T == 0) {
    if (x <= N) {
      for (int i = 1; i <= x; ++i) cnt[S[i] - 'a']++;
    } else {
      for (int i = 1; i <= N; ++i) cnt[S[i] - 'a']++;
      x -= N;
      for (int i = 0; i < 26; ++i) cnt[i] += g[0][i] * (x / T);
      for (int i = 1; i <= x % T; ++i) cnt[S[i] - 'a']++;
    }
  } else {
    while (mx > 1 && x > 0) {
      if (x >= len[mx - 1]) {
	for (int i = 0; i < 26; ++i) cnt[i] += g[mx - 1][i];
	x -= len[mx - 1], mx = mx - 2;
      } else {
	mx = mx - 1;
      }
    }
    for (int i = 1; i <= x; ++i) cnt[S[i] - 'a']++;
  }
}

int main() {
  scanf("%s", S + 1), N = strlen(S + 1);
  N /= 2;
  
  static int f[MAX_N];
  for (int i = 2, j = 0; i <= N; ++i) {
    while (j && S[j + 1] != S[i]) j = f[j];
    if (S[j + 1] == S[i]) j++;
    f[i] = j;
  }

  T = N - f[N];
  i64 l, r;
  scanf("%lld%lld", &l, &r);

  static i64 cnt[2][26];
  work(r, cnt[0]), work(l - 1, cnt[1]);
  for (int i = 0; i < 26; ++i)
    printf("%lld ", cnt[0][i] - cnt[1][i]);
  puts("");
  return 0;
}


Measured memory_bytes: 768
#include<bits/stdc++.h>
using namespace std;
#define MOD (1000000007)
vector<vector<int>> dp(100005,vector<int>(2,0));
int main(){
  string s;
  cin>>s;
  int n=s.length();
  dp[0][0]=1;
  for(int i=0;i<n;++i){
    if(s[i]=='0'){
      dp[i+1]=dp[i];
      (dp[i+1][1]+=dp[i][1]*2%MOD)%=MOD;
    }
    else{
      dp[i+1][1]=(dp[i][0]+dp[i][1])%MOD;
      (dp[i+1][0]+=2*dp[i][0]%MOD)%=MOD;
      (dp[i+1][1]+=2*dp[i][1]%MOD)%=MOD;
    }
  }
  cout<<(dp[n][0]+dp[n][1])%MOD;
}

Measured memory_bytes: 5888
#include <bits/stdc++.h>
 
using namespace std;
 
unordered_set<int64_t> sp;
unordered_set<int64_t> dot;
int64_t H,W;
uint64_t ans[10];
 
int main(){
    int N;
    cin >> H >> W >> N;
    for (int i = 0; i < N; ++i) {
        int A, B;
        scanf("%d %d", &A, &B);
        A--;
        B--;
        dot.insert(((int64_t) A << 32) | B);
        for (int dr = -2; dr <= 0; ++dr) {
            int64_t r = A + dr;
            if (r < 0 || r + 2 >= H) continue;
            for (int dc = -2; dc <= 0; ++dc) {
                int64_t c = B + dc;
                if (c < 0 || c + 2 >= W) continue;
                sp.insert((r << 32) | c);
            }
        }
    }
    for (int64_t pos : sp) {
        int count = 0;
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (dot.find(pos + i * (1LL << 32) + j) != dot.end()) ++count;
            }
        }
        ans[count]++;
    }
    uint64_t sum = 0;
    for (int i = 0; i < 10; ++i) {
        sum += ans[i];
    }
    cout << ((H - 2) * (W - 2) - sum + ans[0]) << endl;
    for (int i = 1; i <= 9; ++i) {
        cout << ans[i] << endl;
    }
}


Measured memory_bytes: 40720
#include <stdio.h>

int ShowHex(long long x)
{
    int  r;
    if(x<26){
      putchar('a'+x);
      return 0;
    }

    r = x % 26;            /* 2６で割った余りをrに保存 */
    x = x / 26;            /* x < 26 なら０になる */

    if (x > 0){           /* x が０でない限り */
        ShowHex(x-1);
      }

      putchar('a' + r);
    return 0;
}

int main(){
  long long input;
  scanf("%lld",&input);
  ShowHex(input-1);
  printf("\n");
  return 0;
}


Measured memory_bytes: 1628
#include <bits/stdc++.h>
#define cin_fit() cin.tie(nullptr);ios::sync_with_stdio(false)
#define rep(i, N) for(int i=0; i<(N); i++)
#define reps(i, N) for(int i=1; i<=(N); i++)
#define rrep(i, N) for(int i=(int)(N)-1; i>=0; i--)
#define rreps(i, N) for(int i=(int)(N); i>=1; i--)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
using namespace std;
using ll = long long;
using V = vector<ll>;
using P = pair<ll, ll>;
constexpr int inf = 1e9;
constexpr int mod = 1e9+7;
ll gcd(ll a, ll b) { return b? gcd(b, a%b) : a;}
ll lcm(ll a, ll b) { return a/gcd(a, b)*b;}

ll W, H, x, y;

int main() {
    cin_fit();
    cin >> W >> H >> x >> y;
    cout << (double)(W / 2.0 * H) << ' ';
    if (2*x == W && 2*y == H) cout << 1;
    else cout << 0;
    return 0;
}


Measured memory_bytes: 256