akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

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

    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;

    vector<int> ans;
    int now = n;
    while (now) {
        bool ok = false;
        for (int i = m; i > 0; i--) {
            if (now - i >= 0 && s[now - i] == '0') {
                ans.push_back(i);
                now -= i;
                ok = true;
                break;
            }
        }
        if (!ok) {
            cout << -1 << endl;
            return 0;
        }
    }
    reverse(ans.begin(), ans.end());
    for (int a : ans) {
        cout << a << ' ';
    }
}


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

int main() {
	int n, m, ans = 0;
	cin >> n >> m;
	for (int i = 1; i*i <= m; i++) {
		if (m%i != 0) continue;
		int a, b;
		a = i;
		b = m / a;
		if ((long long)a*n <= m)
			ans = max(ans, a);
		if ((long long)b*n <= m)
			ans = max(ans, b);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <map>
using namespace std;
#define rep(i,N) for(int i = 0; i<(int)(N); i++)

map<string,int> card;
int main(){
        int N,M;
        string s[100],t[100];
        cin>>N;
        rep(i,N){
                cin>>s[i];
                card[s[i]]++;
        }
        cin>>M;
        rep(i,M){
                cin >> t[i];
                card[t[i]]--;
        }
        int maxnum = 0;
        rep(i,N){
                maxnum = max(maxnum,card[s[i]]);
        }
        cout << maxnum << endl;

        return 0;
}


Measured memory_bytes: 256
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;

public class Main {

	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);

		int m = sc.nextInt();

		out.println(48 - m);
		out.flush();
	}

}

class FastScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (ptr < buflen) return true;
		else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) return false;
		}
		return true;
	}

	private byte readByte() {
		if (hasNextByte()) return buffer[ptr++];
		return -1;
	}

	private boolean isPrintableChar(byte c) {
		return '!' <= c && c <= '~';
	}

	private void skipUnprintable() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr])) {
			ptr++;
		}
	}

	public boolean hasNext() {
		skipUnprintable();
		return hasNextByte();
	}

	public String next() {
		if (!hasNext()) throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		byte b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	public int nextInt() {
		if (!hasNext()) throw new NoSuchElementException();
		int n = 0;
		boolean minus = false;
		byte b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) throw new NumberFormatException();
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}

	public int[] nextIntArray(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}

	public long nextLong() {
		if (!hasNext()) throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		byte b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) throw new NumberFormatException();
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}

	public long[] nextLongArray(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}
}

Measured memory_bytes: 21076
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

class DigitsInMultiplication
{
private:
	long long n;
public:
	DigitsInMultiplication(){
		cin >> n;
	}

	int cout_digits(long long x){
		int digits = 0;
		while(x > 0){
			x /= 10;
			digits++;
		}
		return digits;
	}

	void exec(){
		int ans = 11;
		for (long long i = 1; i*i <= n; i++)
		{
			if(n % i == 0){
				ans = min(ans, max(cout_digits(i), cout_digits(n/i)));
			}
		}
		cout << ans << endl;
	}
};

int main(){
	DigitsInMultiplication dim = DigitsInMultiplication();
	dim.exec();
}

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

using namespace std;

int main(void) {
	int N, input, checkBingo = 0;
	string ans = "No";
	vector<vector<int>> A;
	vector<int> B;
	vector<vector<int>> checkAns;
	for (int i = 0; i < 3; i++) {
		A.emplace_back();
		checkAns.emplace_back();
		for (int j = 0; j < 3; j++) {
			cin >> input;
			A[i].emplace_back(input);
			checkAns[i].emplace_back(0);
		}
	}
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> input;
		B.emplace_back(input);
	}
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < N; k++) {
				if (A[i][j] == B[k]) {
					checkAns[i][j] = 1;
				}
			}
		}
	}
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (checkAns[i][j] == 1) {
				checkBingo++;
			}
		}
		if (checkBingo == 3) {
			ans = "Yes";
		}
		checkBingo = 0;
	}
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (checkAns[j][i] == 1) {
				checkBingo++;
			}
		}
		if (checkBingo == 3) {
			ans = "Yes";
		}
		checkBingo = 0;
	}
	if (checkAns[0][0] == 1 && checkAns[1][1] == 1 && checkAns[2][2] == 1) {
		ans = "Yes";
	}
	if (checkAns[2][0] == 1 && checkAns[1][1] == 1 && checkAns[0][2] == 1) {
		ans = "Yes";
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FAST_IO                       \
	ios_base::sync_with_stdio(false); \
	cin.tie(NULL);                    \
	cout.tie(NULL);
#define pb push_back
#define ll long long

struct Q
{
	ll x, y;
	ll operator*(Q b)
	{
		// cout << x << " "<< y<<endl;
		// cout << b.y << " "<< b.x << endl;
		return (x * b.y - y * b.x);
	}
	void read()
	{
		cin >> x >> y;
	}
	Q operator-(Q b)
	{
		return {x - b.x, y - b.y};
	}
	double operator%(Q b)
	{
		return sqrt(pow(x - b.x, 2) + pow(y - b.y, 2));
	}
};
int main()
{
	FAST_IO
	int n, a, b;
	cin >> n;
	vector <int> num(n),numc(n), num1(n), num2(n);
	for (int i = 0; i < n; i += 1)
	{
		num[i] = i + 1;
		numc[i] = i+1;
	}
	for (int i = 0; i < n; i++)
	{
		cin >> num1[i];
	}

	for (int i = 0; i < n; i++)
	{
		cin >> num2[i];
	}
	int i =0;
	while (true)
	{	
		if (num == num1)
		{
		a = i;
		break;
		}
		next_permutation(num.begin(),num.end());
		i++;
	}
	i=0;
		while (true)
	{	
		if (numc == num2)
		{
		b = i;
		break;
		}
		next_permutation(numc.begin(),numc.end());
		i++;
	}
	cout << abs(b - a)<<endl;
	return 0;
}

Measured memory_bytes: 256
n,m=map(int,input().split())
stores=[]
for i in range(n):
  a,b=map(int,input().split())
  stores.append([a,b])
stores=sorted(stores, key=lambda x: x[0])
ans=0
i=0
while m>0:
  ans+=stores[i][0]*min(m,stores[i][1])
  m-=stores[i][1]
  i+=1
print(ans)

Measured memory_bytes: 63448
#include <iostream>
#include <algorithm>
#include <string>
#include <set>

using namespace std;

int main(){
    string A[3];
    int N;
    cin >> N;
    for(int i = 0; i < 3; ++i){
        cin >> A[i];
    }

    int ans = 0;
    set<char> table[N];
    for(int i = 0; i < 3; ++i){
        int anstmp = 2;
        for(int j = 0; j < N; ++j){
            table[j].insert(A[i][j]);
        }
    }
    for(int i = 0; i < N; ++i){
        ans += table[i].size()-1;
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
//#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cassert>
using namespace std;
typedef long long ll;
const int Nmax = 50;
int N, P, A[Nmax];

ll fact[100];

ll ext_gcd(ll a, ll b, ll &x, ll &y){
	if(b == 0){
		x = 1;
		y = 0;
		return a;
	}
	ll nx, ny;
	ll g = ext_gcd(b, a%b, nx, ny);
	x = ny;
	y = nx - a/b *ny;
	return g;
}

ll inv_mod(ll x, ll p){
	ll y,z;
	ext_gcd(x, p, y, z);
	while(y < 0) y+=p;
	return y;
}

ll fact_mod(ll n, ll p, ll &e){
	// n! = a * p^e
	// return = a % p
	if(n == 0){
		e = 0;
		return 1;
	}

	ll na = fact_mod(n/p, p, e);

	e += n/p;
	ll a = na * fact[n%p] % p;

	if((n/p)%2) a = a * (p-1)%p;
	return a;
}

ll comb_mod(ll n, ll m, ll p){
	ll e1,e2,e3;
	ll a1 = fact_mod(n, p, e1);
	ll a2 = fact_mod(m, p, e2);
	ll a3 = fact_mod(n-m, p, e3);

	if(e1 > e2+e3) return 0;
	else return a1*inv_mod(a2*a3%p, p)%p;
}

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

	fact[0] = fact[1] = 1;
	for(int i=2; i<100; i++) fact[i] = fact[i-1]*i;

	int nodd = 0;
	for(int i=0; i<N; i++) nodd += (A[i]%2);

	ll ans = 0;
	for(int i=0+P; i<=nodd; i+=2){
		ll t = 1;
		for(int j=0; j<i; j++){
			t *= nodd-j;
			t /= j+1;
		}
		//cout << t << endl;
		ans += t;
	}
	//cout << ans << endl;
	for(int i=0; i<N-nodd; i++){
		ans *= 2;
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MOD = 1'000'000'007;
const ld PI = acos(-1);  
const ld EPS = 0.0000000001;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define REP(i, n) for(ll i=0; i<(ll)(n); i++)
#define REPD(i, n) for(ll i=n-1; 0<=i; i--)
#define FOR(i, a, b) for(ll i=a; i<(ll)(b); i++)
#define FORD(i, a, b) for(ll i=a; (ll)(b)<=i; i--)
#define ALL(x) x.begin(), x.end()
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main(){
    ll d;   cin >> d;
    vector<ll> c(26), days(26, 0);
    REP(i, 26) cin >> c[i];
    vector<vector<ll>> s(d, vector<ll>(26, 0));
    REP(i, d) REP(j, 26) cin >> s[i][j];
    REP(q, d){
        ll obj=-1, tmp=-LINF;
        REP(i, 26){
            if(tmp<days[i]*c[i]+s[q][i]){
                if(0<=obj) days[obj] += 1;
                obj = i;
                tmp = days[i]*c[i]+s[q][i];
            }else days[i] += 1;
        }
        cout << obj+1 << endl;
    }
}


Measured memory_bytes: 3724
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1000000007;
#define INF 1LL<<30
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()

int main(){
    while(1){
        int n;
        cin>>n;
        if(n==0) return 0;

        vector<int> imos(90000,0);
        rep(i,n){
            string s,t;
            cin>>s>>t;

            int t1=0;
            t1+=60*60*10*(s[0]-'0')+60*60*(s[1]-'0');
            t1+=60*10*(s[3]-'0')+60*(s[4]-'0');
            t1+=10*(s[6]-'0')+(s[7]-'0');
            t1++;
            int t2=0;
            t2+=60*60*10*(t[0]-'0')+60*60*(t[1]-'0');
            t2+=60*10*(t[3]-'0')+60*(t[4]-'0');
            t2+=10*(t[6]-'0')+(t[7]-'0');
            t2++;

            imos[t1]++;
            imos[t2]--;
        }
        rep(i,90000){
            if(i) imos[i]+=imos[i-1];
        }

        int ans=0;
        rep(i,90000) ans=max(ans,imos[i]);

        cout<<ans<<endl;
    }
}



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

#define REP(i,n) for(ll i=0;i<n;++i)
#define RREP(i,n) for(ll i=n-1;i>=0;--i)
#define FOR(i,m,n) for(ll i=m;i<n;++i)
#define RFOR(i,m,n) for(ll i=n-1;i>=m;--i)
#define ALL(v) (v).begin(),(v).end()
#define PB(a) push_back(a)
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());
#define DUMP(v) REP(aa, (v).size()) { cout << v[a]; if (a != v.size() - 1)cout << " "; else cout << endl; }
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

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


using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll max(ll a, int b) { return max(a, ll(b)); }
ll max(int a, ll b) { return max(ll(a), b); }
ll min(ll a, int b) { return min(a, ll(b)); }
ll min(int a, ll b) { return min(ll(a), b); }
///(?´????????`)(?´????????`)(?´????????`)(?´????????`)(?´????????`)(?´????????`)///
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	vi p(300001, 1);
	p[0] = false;
	p[1] = false;
	p[2] = false;
	p[3] = false;
	p[4] = false;
	p[5] = false;
	FOR(i, 6, p.size()) {
		if (p[i] && (i % 7 == 6 || i % 7 == 1)) {
			for (int j = 1; i*(j * 7 - 1) < 300001; ++j) {
				if (i*(j * 7 - 1) < p.size())p[i*(j * 7 - 1)] = false;
				if (i*(j * 7 + 1) < p.size())p[i*(j * 7 + 1)] = false;
			}
		}
		else {
			p[i] = false;
		}
	}

	while (1) {
		int n;
		cin >> n;
		if (n == 1)break;
		cout << n << ":";
		FOR(i, 1, 300001) {
			if (n%i == 0 && p[i])cout << " " << i;
		}
		cout << endl;

	}
	return 0;
}

Measured memory_bytes: 4008
#include <cstdio>
#include <climits>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <list>
#include <set>
#include <bitset>
#include <iterator>
#define loop(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define debug(x)  cout << #x << " = " << (x) << endl;

using namespace std;
using LL = long long;
using ULL = unsigned long long;

const int MOD = 1000000007;
int h, w, k;

LL solve() {
    --k;

    vector<vector<LL>> dp(h + 1, vector<LL>(w, 0));
    // dp[i][j] := 縦棒をうえから i 刻み分についての入れ方のうち、1 から
    // スタートして j で終わるようなものの個数

    dp[0][0] = 1;
    rep(i, h) {
        rep(j, w) {
            rep(bit, 1 << (w - 1)) {
                bool ok = true;

                rep(k, w - 2) {
                    if ( (bit & (1 << k)) and (bit & (1 << (k + 1))) ) {
                        ok = false;
                    }
                }

                if (not ok) continue;
                int nj = j;
                if (bit & (1 << j)) nj = j + 1;
                else if (j > 0 and (bit & (1 << (j - 1)))) nj = j - 1;
                dp[i + 1][nj] += dp[i][j] % MOD;
                dp[i + 1][nj] = dp[i + 1][nj] % MOD;
            }
        }
    }
    return dp[h][k];
}
int main() {
    cin >> h >> w >> k;
    cout << solve() << endl;
    return 0;
}


Measured memory_bytes: 256
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}
fn main(){
    let n : i64 = read();
    let ans = (1..n+1).fold(0,|y,x| y + x);
    println!("{}",ans );
}

Measured memory_bytes: 4352
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <queue>
#include <bitset>

typedef long long ll;

int main(int argc, char* argv[])
{
  int a, b, c, x, y;
  std::vector< int > vi;
  int sum1 = 0;
  int sum2 = 0;
  std::cin >> a >> b >> c >> x >> y;
  int p1 = std::min(x, y);

  if (a+b < c*2) {
    sum1 += p1 * (a+b);
  } else {
    sum1 += p1 * c * 2;
  }

  if (x > y) {
    sum1 += (x-y) * a;
  } else {
    sum1 += (y-x) * b;
  }

  sum2 = c * 2 * std::max(x, y);

  std::cout << std::min(sum1, sum2) << std::endl;

  return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3")
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,n) for(int i=1;i<=n;i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define EPS (1e-9)
#define INF (1e17)
#define PI (acos(-1))
//const double PI = acos(-1);
//const double EPS = 1e-15;
//long long INF=(long long)1E17;
#define i_7 (long long)(1e9+7)
//#define i_7 998'244'353
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
long long po(long a, long b){
    if(b==0){
        return 1;
    }
    
    long long z = po(a,b/2);
    z = mod(z*z);
    if(b%2!=0){
        z = mod(a*z);
    }
    return z;
}

bool prime_(int n){
  if(n==1){
    return false;
  }else if(n==2){
    return true;
  }else{
    for(int i=2;i<=std::sqrt(n);i++){
      if(n%i==0){
        return false;
      }
    }
    return true;
  }
}

long long gcd_(long long a, long long b){
  if(a<b){
    std::swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd_(b,a%b);
  }
}
 
long long lcm_(long long x, long long y){
  return (x/gcd_(x,y))*y;
}

//using namespace std;
//using namespace boost::multiprecision;
//using namespace __gnu_pbds;

int main(){
  using namespace std;
  int h,w,n;
  cin>>h>>w>>n;
  int ans = min((n+h-1)/h, (n+w-1)/w);
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double lb;
#define REP(i,j,n) for (int i=j;i<(n);i++)
#define RREP(i,n) for (int i = n; 0<i;i--)
#define print(out) cout<< out  << "\n";
#define mod 1000000007
const int INF = 1e9;

int main(){
  
  set<int> s;
  int N,a;cin>>N;
  REP(i,0,N){
    cin>>a;
    s.insert(a);
  }
  print((s.size()==N?"YES":"NO"))
}


Measured memory_bytes: 9600
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair< ll, ll > Pi;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define rep3(i,i0,n) for(int i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
const ll INF = 1LL << 60;
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; }
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;}
#define all(x) x.begin(), x.end()
#define mp make_pair
bool compare(Pi a, Pi b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}


bool In_map(ll y,ll x,ll h,ll w){
    if(y<0 || x<0 || y>=h || x>=w){
        return 0;
    }else{
        return 1;
    }
}
const vector<ll> dx{1,0,-1,0};
const vector<ll> dy{0,1,0,-1};


int main() {
    string S,T;
    cin >>S>>T;
    map<char,ll>m1;
    map<char,ll>m2;
    rep(i,S.size()){
        if(m1[S[i]]!=m2[T[i]]){
            cout<<"No"<<endl;
            return 0;
        }
        m1[S[i]] =i+1;
        m2[T[i]] =i+1;
    }
    cout << "Yes" << endl;


    return 0;
    

}

Measured memory_bytes: 3936
/**
  *  Matrix Chain Multiplication
  * ??£??????????????????(Matrix-Chain Multiplication problem)
  */
  

#include <stdio.h>
#include <limits.h>

int MATRIX[101][101];
int p[101];
int n;

void matrixChain();
int min(int, int);

main() {
  int i, x, y;

  scanf("%d", &n);
  for(i = 0; i < n; i++) {
    scanf("%d %d", &y, &x);
    if(i == 0) { //???????????????????????¨??§
      p[i] = y;
      p[i + 1] = x;
    } else {
      p[i + 1] = x;
    }
  }
  
  matrixChain();
  
  printf("%d\n", MATRIX[1][n]);
  
  return 0;
}


int min(int x, int y) {
  if(x >= y) {
    return y;
  } else {
    return x;
  }
}

void matrixChain() {
  int i, j, k, l, q;
  /* initialize */
  for(i=1;i<n+1;i++) {
    MATRIX[i][i] = 0;
  }
  
  /**/
  for(l=2;l<n+1;l++) {
    for(i=1;i<n-l+2;i++) {
      j = i + l - 1;
      MATRIX[i][j] = INT_MAX;
      for(k=i;k<j;k++) {
        q = MATRIX[i][k] + MATRIX[k + 1][j] + p[i - 1] * p[k] * p[j];
        MATRIX[i][j] = min(MATRIX[i][j], q);
      }
    }
  }
}

Measured memory_bytes: 636
#include <bits/stdc++.h>
using namespace std;
int main() {
    int N; cin >> N;
    vector<int> A(N), B(N), C(N);
    for(int i = 0; i < N; i++) {
        cin >> A[i];
    }

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

    for(int i = 0; i < N-1; i++) {
        cin >> C[i];
    }

    int ans = 0;
    for(int i = 0; i < N; i++) {
        ans += B[A[i]-1];
    }

    for(int i = 0; i < N-1; i++) {
        if(A[i]+1 == A[i+1]) ans += C[A[i]-1];
    }
    cout << ans;
    return 0;
}

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

using namespace std;
using ll = long long;

double expected_value(int n) {
  return (double)((1 + n) * n / 2) / (double)n;
}

int main() {
  int n, k;
  cin >> n >> k;
  vector<double> ps(n + 1);
  vector<double> comsum(n + 1, 0);
  int p;
  rep(i, n) {
    cin >> p;
    ps[i + 1] = expected_value(p);
    comsum[i + 1] = comsum[i] + ps[i + 1];
  }
  double mm = 0;
  for (int i = k; i <= n; i++) {
    mm = max(comsum[i] - comsum[i - k], mm);
  }
  printf("%.6f\n", mm);
  return 0;
}


Measured memory_bytes: 6432
#include <stdio.h>

int main(void){
  int n = 0;
  int count = 0;
  int flag = 0;

  scanf("%d",&n);

  int y[n];
  
  for(int i = 0;i < n;i++){
    scanf("%d",&y[i]);
  }

  while(flag == 0){
    for(int i = 0;i < n;i++){
     if(y[i] % 2 == 1){
         flag = 1;
      }
      y[i] = y[i] / 2;
    }
    if(flag == 0) count++;
  }
  printf("%d\n",count);


  return 0;
}

Measured memory_bytes: 128
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <array>
#include <bitset> 
#include <unordered_map>

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

int main() {
	int M,K;
	cin >> M >> K;
	if(K==0){
		auto sp="";
		for(int i=0;i<(1<<M);i++){
			cout << sp << i << " " << i;
			sp=" ";
		}
		cout << endl;
		return 0;
	}
	if(K>=(1<<M)){
		cout << -1 << endl;
		return 0;
	}
	vector<int> u;
	for(int i=1;i<(1<<M);i++){
		if(i!=K){
			u.push_back(i);
			u.push_back(K^i);
			break;
		}
	}
	if(u.size()<2){
		cout << -1 << endl;
		return 0;
	}
	cout << K;
	for(int t:u){
		cout << " " << t;
	}
	for(int i=0;i<(1<<M);i++){
		if(i==K)continue;
		auto it=lower_bound(u.begin(),u.end(),i);
		if(it!=u.end()&&*it==i)continue;
		cout << " " << i;
	}
	cout << " " << K;
	for(int i=(1<<M)-1;i>=0;i--){
		if(i==K)continue;
		auto it=lower_bound(u.begin(),u.end(),i);
		if(it!=u.end()&&*it==i)continue;
		cout << " " << i;
	}
	reverse(u.begin(),u.end());
	for(int t:u){
		cout << " " << t;
	}
	cout << endl;


	return 0;
}



Measured memory_bytes: 1792
#include<iostream>
#include<cstring>

using namespace std;

// http://d.hatena.ne.jp/Nekonyan/20110508 
// Nekonyan?????????????????????????????????????????????

int table[10+1][10000];
int memo[10];

void numnum (int size, int depth, int sum )
{
	if (size + 1 == depth ) {
		table[size][sum]++;
	}else{
		for (int i = 0; i <= 9; ++i ){
			if ( memo[i] == 0 ) {
				memo[i] = 1;
				numnum (size, depth + 1, sum + i*depth );
				memo[i] = 0;
			} // end if
		} // end for
	} // end if
}

int main()
{
	memset(table, 0, sizeof (table ) );

	for (int i = 1; i <= 10; ++i ) {
		memset (memo, 0, sizeof (memo ) );
		numnum (i, 1, 0 );
	} // end for

	int n, s;
	while ( cin >> n >> s ) {
		cout << table[n][s] << endl;
	} // end while

	return 0;
}

Measured memory_bytes: 1596
#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <random>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repp(i,n,m) for (int i = m; i < (n); ++i)
#define repl(i,n) for (long long i = 0; i < (n); ++i)
#define reppl(i,n,m) for (long long i = m; i < (n); ++i)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using PL = pair<long long, long long>;
using Pxy = pair<double, double>;
using T = tuple<int, int, bool>;
const int INF = 1001001007;
const int mod = 1000000007;
const int MOD = 998244353;
const ll inf = 1e18;
template <typename AT>
void printvec(vector<AT> &ar){
    rep(i,ar.size()-1) cout << ar[i] << " ";
    cout << ar[ar.size()-1] << endl;
}
template <typename Q>
void printvvec(vector<vector<Q>> &ar){
    rep(i,ar.size()){
        rep(j,ar[0].size()-1) cout << ar[i][j] << " ";
        cout << ar[i][ar[0].size()-1] << endl;
    }
}
template <typename S>
bool range(S a, S b, S x){
    return (a <= x && x < b);
}

void yes(){
    cout << "Yes" << endl;
}

void no (){
    cout << "No" << endl;
}

ll cel (ll a, ll b){
    if (a % b == 0) return a / b;
    else return a / b + 1;
}

ll gcds(ll a, ll b){
    ll c = a % b;
    while (c != 0){
        a = b;
        b = c;
        c = a % b;
    }
    return b;
}

struct vs{
    int ip;
    int sh;
    vector<ll> scs;
    vector<ll> rui;
    ll koho;
};


int main() {
    int n; cin >> n;
    ll k; cin >> k;
    vector<int> ar(n);
    rep(i,n){
        int a; cin >> a;
        ar[i] = a-1;
    }
    vector<ll> sc(n);
    vector<vs> arv(n);
    rep(i,n){
        arv[i].ip = i;
    }
    rep(i,n) cin >> sc[i];
    rep(i,n){
        int ima = i;
        int cnt = 1;
        ima = ar[ima];
        arv[i].scs.emplace_back(sc[ima]);
        while (ima != i){
            ima = ar[ima];
            arv[i].scs.emplace_back(sc[ima]);
            cnt++;
        }
        arv[i].sh = cnt;
        arv[i].rui.resize(cnt);
        arv[i].rui[0] = arv[i].scs[0];
        rep(j,cnt-1){
            arv[i].rui[j+1] = arv[i].rui[j] + arv[i].scs[j+1];
        }
        if (arv[i].rui[cnt-1] <= 0){
            ll ans = arv[i].rui[0];
            rep(j,min(ll(cnt-1),k-1)){
                ans = max(ans,arv[i].rui[j+1]);   
            }
            arv[i].koho = ans;
        }
        else {
            ll ans = k / cnt * arv[i].rui[cnt-1] - arv[i].rui[cnt-1];
            ll pl = 0LL;
            ll imap = 0LL;
            rep(j,k % cnt + cnt){
                imap += arv[i].scs[j % cnt];
                pl = max(pl,imap);
            }
            arv[i].koho = ans + pl;
        }
    }
    ll lans = -1000000000000000;
    rep(i,n){
        lans = max(lans,arv[i].koho);
        //cout << arv[i].koho << endl;
    }
    cout << lans << endl;
}

Measured memory_bytes: 414568
#include <string.h>
#include <stdio.h>
int main (){
  int strLen,i;
  char p1[11];
  char p2[11];
  scanf("%s",p1);
  scanf("%s",p2);
  strLen = (int)strlen(p1);
  if(strcmp(p1,p2) == 0){
	printf("No");
    return 0;
  }
  for(i = 0;i < strLen;i++){
	if(p1[i] != p2[i]){
      printf("No");
      return 0;
    }
  }
  printf("Yes");
  return 0;
}

Measured memory_bytes: 1732
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
int main()
{
   long a,b;
   long i,j,k;
   long f;
   long n;
   long cnt = 0;
   long h;
   long left,right,mid;
   long ans = 0;
   static char str[102][1003];
   char s[9];
   char p[1003];
   char tmp;
   int end = 0;
   scanf("%ld %ld",&a,&b);
   printf("%ld %ld\n",a*b,2*a+2*b);


   return 0;
}

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

//組み合わせの数nCrを計算
ll nCr(ll n, ll r)
{
    ll num = 1;
    for (ll i = 1; i <= r; i++)
    {
        num = num * (n - i + 1) / i;
    }
    return num;
}

int main()
{
    int n, p;
    cin >> n >> p;
    int x = 0, y = 0;
    rep(i, n)
    {
        int a;
        cin >> a;
        if (a % 2 == 0)
            x++;
        else
            y++;
    }

    ll ans = pow(2, x);
    if (p == 0)
    {
        ll tmp = 0;
        for (int i = 0; i <= y; i += 2)
        {
            tmp += nCr(y, i);
        }
        ans *= tmp;
    }

    if (p == 1)
    {
        ll tmp = 0;
        for (int i = 1; i <= y; i += 2)
        {
            tmp += nCr(y, i);
        }
        ans *= tmp;
    }

    cout << ans << endl;
}

Measured memory_bytes: 4068
#include<stdio.h>
 
int main(void){
  int i;
  int n;
  int m;
  int a[10010];
  scanf("%d%d",&n, &m);
  for(i = 0; i < m; i++){
    scanf("%d", &a[i]);
    n -= a[i];
  }
  if (n < -1)
    n=-1;
  printf("%d",n);
}

Measured memory_bytes: 2192
#include <bits/stdc++.h>
#define rep(i,cc,n) for(int i=cc;i<=n;++i)
using namespace std;
const int INF = 1001001001;

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

  vector<int> s(N);
  rep(i,0,N-1) cin >> s[i];

  int ans = accumulate(s.begin(), s.end(), 0);
  if (ans % 10 == 0) {
    int p = INF;
    rep(i,0,N-1) {
      if (s[i] % 10 != 0) p = min(p,s[i]);
    }
    if (p == INF) ans = 0;
    else ans -= p;
  }

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


Measured memory_bytes: 256
#include <iostream>
long long xor_0_to_n(long long n)
{
    if (n < 0) return 0;
    switch (n % 4) {
        case 0:
            return n;
        case 1:
            return 1;
        case 2:
            return n + 1;
        case 3:
            return 0;
    }
}
int main()
{
    long long a, b;
    std::cin >> a >> b;
    std::cout << (xor_0_to_n(a - 1) ^ xor_0_to_n(b)) << std::endl;
}


Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
typedef tuple<int, int, int> T;
int main() {
    int N, Q;
    cin >> N >> Q;
    vector<T> v(N);
    for (int i = 0; i < N; i++) {
        int s, t, x;
        cin >> s >> t >> x;
        v[i] = T(x, s, t);
    }
    sort(v.begin(), v.end());
    vector<int> D(Q);
    set<int> se;
    se.insert(2e9);
    for (int i = 0; i < Q; i++) {
        cin >> D[i];
        se.insert(D[i]);
    }
    map<int, int> ma;
    for (int i = 0; i < N; i++) {
        int x = get<0>(v[i]), s = get<1>(v[i]), t = get<2>(v[i]);
        int l = s - x;
        int r = t - x;
        while (1) {
            auto itr = se.lower_bound(l);
            if (*itr >= r) break;
            ma[*itr] = x;
            se.erase(*itr);
        }
    }
    for (int i = 0; i < Q; i++) {
        int p = ma[D[i]];
        cout << (p ? p : -1) << endl;
    }
}


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

using namespace std;

int main() {
	string s;
	cin >> s;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == ',') {
			cout << ' ';
		} else {
			cout << s[i];
		}
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define mod 1000000007
#define null NULL
#define test cout<<"#"
#define maX 1000000000
 
ll ans[100001];

void solve(vector<ll> &w, vector<ll> &v, ll n, ll wt)
{	
	for(ll x = 0; x < n; x++)
	{
		for(ll y = wt; y>=0; y--)
		{
			if(w[x]<=y)
				ans[y] = max(ans[y], ans[y - w[x]]+v[x]);
		}
	}
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
	memset(ans, 0, sizeof(ans));
    ll n, w;
	cin>>n>>w;
    vector<ll> a(n);
	vector<ll> b(n);
    for(ll x = 0; x < n; x++)
	{
		cin>>a[x];
		cin>>b[x];
	}
	solve(a, b, n, w);
	cout<<ans[w];
}

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

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

  int base = 7;
  int sum = 0;
  rep(i,0,K-1)
  {
    sum = base % K;
    base = sum * 10 + 7;
    if (sum == 0)
    {
      cout << i + 1 << endl;
      return 0;
    }
  }

  cout << -1 << endl;
  return 0;
}


Measured memory_bytes: 3608
d={}
n=int(input())
a=list(map(int,input().strip().split(" ")))
ans=0
for i in a:
    if i not in d:
        d[i]=1
    else:
        d[i]=d[i]+1
for i in d.values():
    ans+=(i*(i-1))//2

for j in a:
    d[j]-=1
    
    if ans>0:
        ans-=d[j]
        print(ans)
        ans+=d[j]
        d[j]+=1
    elif ans==0:
        print(0)
    
    

        


Measured memory_bytes: 25716
#include <bits/stdc++.h>
using namespace std;
constexpr int lcm(int a,int b){return b?lcm(b,a%b):a;}
constexpr int gcd(int a,int b){return a*b/lcm(a,b);}

int main(void){
    string a,b;
    cin>>a>>b;
    sort(a.begin(),a.end());
    sort(b.rbegin(),b.rend());
    cout<<(a<b?"Yes":"No")<<endl;
}


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

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

    vector<int> a(n), b(n), c(n - 1);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
    }
    for(int i = 0; i < n; i++) cin >> b[i];
    for(int i = 0; i < n - 1; i++) cin >> c[i];

    int ans = 0;
    for(int i = 0; i < n; i++) {
        ans += b[a[i]];
        if((i > 0) && (a[i] == a[i - 1] + 1)) ans += c[a[i] - 1];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
    
# 遅延評価で加えてあげるだけ
    
N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]
    
graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)
    
value = [0] * (N+1)
for p,x in PX:
    value[p] += x
    
def dfs(v,parent,add):
    value[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x,v,value[v])
    
dfs(1,0,0)
    
answer = ' '.join(map(str,value[1:]))
print(answer)

Measured memory_bytes: 285828
#include <cstdio>
#include <iostream>
#include <queue>
#include <map>  
#include <algorithm>
using namespace std;
int main() {
	while (1) {
		int a[10][10000];
		int r, c, ki = 1;
		for (int i = 0; i < 10; i++) { for (int j = 0; j < 10000; j++)a[i][j] = -1; }
		cin >> r >> c; if (r == 0)break;
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++)
				cin >> a[i][j];
		}int ans = 0;
		for (int i = 0; i < (1 << r); i++) {
			int tmp = 0;
			for (int j = 0; j < c; j++) {
				int cnt = 0;
				for (int k = 0; k < r; k++) {
					if (a[k][j] + ((i >> k) & 1) == 1)cnt++;
				}cnt = max(cnt, r - cnt);
				tmp += cnt;
			}
			ans = max(ans, tmp);
		}cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 1552
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] a){

		String str;
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		try {
			while(null != ( str = bf.readLine() )){
				char[] cArr = str.toCharArray();
				int len = cArr.length;
				for(int i = 0; i < len / 2; i++){
					char tmp = cArr[i];
					cArr[i] = cArr[len - i - 1];
					cArr[len - i - 1] = tmp;
				}
				for(char c : cArr){
					System.out.print(c);
				}
				System.out.println("");
			}
		} catch (IOException e) {
			e.printStackTrace();
		} finally {
			try {
				bf.close();
			} catch (IOException e) {
			}
		}
	}

}

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

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;

int main() {
  ll N;
  cin >> N;
  vector<ll> v(N);
  ll t = 0LL;
  for(ll i = 0LL; i < N; i++) {
    cin >> v.at(i);
    chmax(t, v.at(i));
  }
  double s = 1000000000;
  
  ll u = 0LL;
  for(ll i = 0LL; i < N; i++) {
    if(t == v.at(i)) continue;
    double d = v.at(i) - ((double)t/2);
    if(chmin(s,abs(d))) u=v.at(i);
  }
  cout << t << " " << u << endl;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double PI = acos(-1);
const ll MOD = 1000000007;

int main() {
  int N,K; cin >> N >> K;
  vector<int> A(N);
  for (int i = 0; i < N; i++) cin >> A[i];
  
  vector<int> B(2e5+1);
  for (int i = 0; i < N; i++) B[A[i]]++;
  
  sort(B.begin(),B.end());
  
  int k;
  k = upper_bound(B.begin(),B.end(),0) - B.begin();
  
  int ans = 0;
  if (2e5 + 1 - k > K) {
    for (int i = 0; i < 2e5 + 1 - K - k; i++) ans += B[k+i];
  }
  
  cout << ans << endl;
}

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

#define rep(i, a, b) for (int i = a; i < (int)(b); ++i)
#define rrep(i, a, b) for (int i = b - 1; i >= (int)(a); --i)

using namespace std;

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;

int main() {
    string s, t, u;
    int a, b;

    cin >> s >> t;
    cin >> a >> b;
    cin >> u;

    if (u == s) {
        cout << a - 1 << " " << b << endl;
    } else {
        cout << a << " " << b - 1 << endl;
    }
    return 0;
}

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

Int N, M, Q;
vector<Int> a(50),b(50),c(50),d(50);

Int dfs(vector<Int> A) {
    if (A.size() == N) {
        Int ans = 0;
        rep(i,Q) {
            if (A[b[i]] - A[a[i]] == c[i]) ans += d[i];
        }
        return ans;
    }
    else {
        Int res = 0;
        for (Int i = A[A.size()-1]; i <= M; i++) {
            A.push_back(i);
            res = max(res, dfs(A));
            A.pop_back();
        }
        return res;

    }
}

int main(){ 

    cin >> N >> M >> Q;


    rep(i,Q) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        a[i]--; b[i]--;
    }


    Int ans;

    vector<Int> A(1,1);

    ans = dfs(A);

    cout << ans << endl;


    return 0;
}


Measured memory_bytes: 3632
#include <iostream>
#include <algorithm>
#include <string>

int n;
std::string s;
int main(){
  std::cin>>n>>s;
  
  int d=0,x=0;
  for(size_t i=0,end=s.size();i<end;++i){
    if(s[i]=='(')
      ++d;
    else
      --d;
    x=std::min(x,d);
  }
  if(x<0)
    s=std::string(-x,'(')+s;
  if(d-x>0)
    s+=std::string(d-x,')');
  std::cout<<s<<std::endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define title "title"
#define ll long long
#define ull unsigned ll
#define fix(x) fixed<<setprecision(x)
#define pii pair<ll,ll>
#define vint vector<ll>
#define pb push_back
using namespace std;
void Freopen(){
	freopen(title".in","r",stdin);
	freopen(title".out","w",stdout);
}
ll read(){
	ll g=0,f=1;
	char ch=getchar();
	while(ch<'0'||'9'<ch){if(ch=='-')f=-1;ch=getchar();}
	while('0'<=ch&&ch<='9'){g=g*10+ch-'0';ch=getchar();}
	return g*f;
}
const ll N=2e5+5;
const ll mod=1e9+7;
ll n,a[N],cnt[N],inv[N],d[N],zero[N],ztot,pos[N],res=1,ans,inv2;
struct Bit{
	ll su[N],size[N];
	ll lowbit(ll x){return x&(-x);}
	void insert(ll x,ll y){for(ll i=x;i<=n;i+=lowbit(i))su[i]=(su[i]+y)%mod,size[i]++;}
	ll query_su(ll x){ll re=0;for(ll i=x;i;i-=lowbit(i))re=(re+su[i])%mod;return re;}
	ll query_size(ll x){ll re=0;for(ll i=x;i;i-=lowbit(i))re+=size[i];return re;}
	void clear(){memset(su,0,sizeof(su)),memset(size,0,sizeof(size));}
}bit;
ll ksm(ll x,ll y){
	ll re=1;
	while(y){
		if(y&1)re=re*x%mod;
		x=x*x%mod;y>>=1;
	}return re;
}
signed main(){
	n=read();
	for(ll i=1;i<=n;i++)a[i]=read();
	for(ll i=1;i<=n;i++)cnt[a[i]]++;
	for(ll i=n;i>=1;i--)cnt[i-1]+=cnt[i];
	for(ll i=1;i<=n;i++)cnt[i]-=n-i;
	for(ll i=1;i<=n;i++)res=res*cnt[i]%mod;
	d[0]=1;inv2=ksm(2,mod-2);
	for(ll i=1;i<=n;i++){
		ll x=(cnt[i]-1)*ksm(cnt[i],mod-2)%mod;
		if(!x)++ztot,zero[i]=ztot,pos[ztot]=i,d[i]=d[i-1];
		else zero[i]=ztot,d[i]=d[i-1]*x%mod;
		inv[i]=ksm(d[i],mod-2);
	}
	for(ll i=1;i<=n;i++){
		ans=(ans+(bit.query_su(a[i])-bit.query_su(pos[zero[a[i]]])+mod)*d[a[i]]%mod*res%mod*inv2%mod)%mod;
		bit.insert(a[i],inv[a[i]]);
	}bit.clear();
	for(ll i=n;i>=1;i--){
		ans=(ans-(bit.query_su(a[i]-1)-bit.query_su(pos[zero[a[i]]])+mod)*d[a[i]]%mod*res%mod*inv2%mod+mod)%mod;
		ans=(ans+bit.query_size(a[i]-1)*res%mod)%mod;
		bit.insert(a[i],inv[a[i]]);
	}return cout<<ans,signed();
}

Measured memory_bytes: 16128
flg=0
i=1
in_data=input()
in_data=int(in_data)
while flg==0:
    if not in_data==0:
        print("Case"+" "+str(i)+": "+str(in_data))
        i=i+1
        in_data=input()
        in_data=int(in_data)
    else:
        flg=1



Measured memory_bytes: 5608
#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<complex>
#include<string.h>
#include<algorithm>
#include<set>
#include<map>
#include<cmath>
#define MS(ptr,val) memset(ptr,val,sizeof(ptr));
#define INPUT(n,m) int n,m;scanf("%d%d",&n,&m);

using namespace std;
typedef long long ll;
const int maxn = 100000;
struct st
{
	int num, ord;
};
st arr[maxn];
bool cmp(st x, st y)
{
	return x.ord < y.ord;
}

int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &arr[i].ord);
		arr[i].num = i;
	}
	sort(arr, arr + n, cmp);
	for (int i = 0; i < n; i++)
		printf("%d ", arr[i].num + 1);
	
	return 0;
}

Measured memory_bytes: 1536
using System;
using System.Linq;
using System.Collections.Generic;

public class Hello
{
    static void Main()
    {
        string[] s_data = Console.ReadLine().Split(' ');
        int word_num = int.Parse(s_data[0]);
        int spell_num = int.Parse(s_data[1]);

        var word_data = new List<string>();
        for(int i = 0; i < word_num; i++) word_data.Add(Console.ReadLine());

        var sort_word_list = word_data.Select(x => x).OrderBy(x => x);
        foreach (var x in sort_word_list) Console.Write(x);
        Console.WriteLine();
    }
}

Measured memory_bytes: 13660
#include<stdio.h>
#include<stdlib.h>

struct node{
	struct node *right;
	struct node *left;
	struct node *parent;
	int key;
};

typedef struct node * Node;

#define NIL NULL


Node root;
 
Node treeMinimum (Node x ){
 
}
 
Node treeSearch (Node u, int k ){
    if (u == NIL || u->key == k ) return u;
    else
    if (u->key < k ){
        return treeSearch (u->right, k );
    }else{
        return treeSearch (u->left, k );
    } // end if 
}
 
Node treeSuccessor (Node x ){
 
}
 
void treeDelete (Node z ){
    Node y; // node to be deleted
    Node x; // child of y
}
 
void insert (int k ){
    Node y = NIL;
    Node x = root;
    Node z;
 
    z = malloc (sizeof (struct node ) );
    z->key = k;
    z->left = NIL;
    z->right = NIL;
 
    if (x == NIL ){
        root = z;
    }else{
        do{
            if (x->key < k ){
                y = x->right;
            }else{
                y = x->left;
            } // end if
 
            if (y != NIL ){
                y->parent = x;
            }else{
                if (x->key < k )
                    x->right = z;
                else
                    x->left = z;
            } // end if
            x = y;
        }while (x != NIL ); // end while
    } // end if
}
 
void inorder (Node u ){
    if (u == NIL ) return;
    inorder (u->left );
    printf (" %d", u->key );
    inorder (u->right );
}
 
void preorder (Node u ){
    if (u == NIL ) return;
    printf (" %d", u->key );
    preorder (u->left );
    preorder (u->right );
}
 
int main()
{
    int n, i, x;
    char com[20];
 
    root = NIL;
    scanf ("%d", &n );
    for (i = 0; i < n; i++ ){
        scanf ("%s", com );
        if (com[0] == 'i' ){    // case insert 
            scanf ("%d", &x );
            insert (x );
        }else
        if (com[0] == 'p' ){ // case print
            inorder (root );
            printf ("\n" );
            preorder (root );
            printf ("\n" );
        }else
        if (com[0] == 'f' ){    // case find
            scanf ("%d", &x );
            Node t = treeSearch (root, x );
            if ( t != NIL ) printf ("yes\n" );
            else printf ("no\n" );
        } // end if
    } // end for
 
    return 0;
}


Measured memory_bytes: 20488
package main

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

func main() {
	c := make([][]int, 3)
	for i := 0; i < 3; i++ {
		c[i] = ReadInts(3)
	}
	x := make([]int, 3)
	y := make([]int, 3)
	for i := 0; i < 3; i++ {
		y[i] = c[0][i] - x[0]
	}
	for i := 0; i < 3; i++ {
		x[i] = c[i][0] - y[0]
	}
	ok := true
	for i := 0; i < 3; i++ {
		for j := 0; j < 3; j++ {
			if x[i]+y[j] != c[i][j] {
				ok = false
			}
		}
	}
	if ok {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int)       { Scan(&i); return }
func ReadString() (s string) { Scan(&s); return }
func ReadInts(n int) []int {
	v := make([]int, n)
	for i := 0; i < n; i++ {
		Scan(&v[i])
	}
	return v
}


Measured memory_bytes: 1840
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for (int i=0;i < (int)(n);i++)

int main(){
    ll h;
    cin >> h;
    ll t=1;
    ll ans=0LL;
    while (h >=1){
        if (h==1){
           ans+=t;
           break;
        }
        else{
            ans+=t;
            h/=2;
            t*=2;
        }
    }
    cout << ans << endl;
    return 0;
}


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


typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ld;

typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int MAXN = 1e6 + 3;

#define _  %  MOD
#define __ %= MOD

#define      each(it,s)        for(auto it = s.begin(); it != s.end(); ++it)
#define      sortA(v)          sort(v.begin(), v.end())
#define      sortD(v)          sort(v.begin(), v.end(), greater<auto>())
#define      fill(a)           memset(a, 0, sizeof (a))

#define      swap(a,b)        {a=a+b;b=a-b;a=a-b;}
#define      rep(i, n)         for(ll i = 0; i < (n); ++i)
#define      repA(i, a, n)     for(ll i = a; i <= (n); ++i)
#define      repD(i, a, n)     for(ll i = a; i >= (n); --i)
#define watch(x) cout << (#x) << " is " << (x) <<endl

#define fi first
#define se second
#define mp make_pair
#define pb push_back

#define fbo find_by_order
#define ook order_of_key

ll gcd(ll a,ll b){if(b==0) return a; else return gcd(b,a%b);}
ll power(ll x,ll y){ll res=1; while(y>0){if(y&1) res=(res*x)%INF;y=y>>1;x=(x*x)%INF;}return res%INF;} // modular exponent
ll inv(ll x)
{
  return power(x,INF-2);
}
ll n,k;
const int maxn=2e5+5;
ll fact[maxn];
ll invfact[maxn];
void work()
{
  fact[1]=1;fact[0]=1;
  invfact[1]=1;invfact[0]=1;
  repA(i,2,maxn-1)
  {
    fact[i]=(i*fact[i-1])%INF;
    invfact[i]=inv(fact[i]);
  }
}
ll C(ll n,ll r)
{
  if(r>n) return 0ll;
  ll ans=1ll;
  ans*=fact[n];
  ans%=INF;
  ans*=invfact[r];
  ans%=INF;
  ans*=invfact[n-r];
  ans%=INF;
  return ans;
}
int main()
{
    ios_base::sync_with_stdio(false); // don't use printf and scanf
    cin.tie(NULL); // cout<<fixed<<setprecision
    work();
    cin>>n>>k;
    k=min(k,n-1);
    ll ans=0;
    repA(i,0,k)
    {
      ll val=1;
      val*=C(n,(ll)i);
      val%=INF;
      val*=C(n-1,(ll)i);
      val%=INF;
      ans+=val;
      ans%=INF;
    }
    cout<<ans<<'\n';
    return 0;
}
// JUST ASK YOURSELF DID YOU GIVE YOUR BEST ? ISSE ZYADA
// KUCH KAR BHI NAHI SAKTE !! ENJOY AND GIVE YOUR BEST!!


Measured memory_bytes: 6768