akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
 
using namespace std;
 
typedef long long ll;
const ll mod = 1000000007;
const int mugen = 1000001000;
int dp[1010][10010];
 
int main() {
    int h,n;
    scanf("%d %d",&h,&n);
    vector<int> a,b;
    for (int i = 0; i < n; i++) {
        int x,y;
        scanf("%d %d",&x,&y);
        a.push_back(x),b.push_back(y);
    } 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= h; j++) {
            dp[i][j] = -mugen;
        }
    }
    for (int i = 0; i < n; i++) {    
        for (int j = 0; j <= h; j++) {
            if (j <= a[i]) dp[i + 1][j] = max(dp[i][j],-b[i]);
            else dp[i + 1][j] = max(dp[i][j], dp[i + 1][j - a[i]] - b[i]); 
        }
    }
    printf("%d\n",-dp[n][h]);
}

Measured memory_bytes: 39424
import java.util.Scanner;
class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
		String dayofweek = sc.next();
		System.out.println(7-week(dayofweek));
  }
  public static int week(String day){
		String[] days = {"SUN","MON","TUE","WED","THU","FRI","SAT"};
		for(int i = 0; i < 7; i++){
			if(day.equals(days[i])){
				return i;
			}
		}
		return 6;
  }
}


Measured memory_bytes: 21972
#include <bits/stdc++.h>
using namespace std;
struct Edge {
    int to;     // 辺の行き先
    int weight; // 辺の重み
    Edge(int t, int w) : to(t), weight(w) { }
};
using Graph = vector<vector<int> >;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reprep(i,j,h,w) rep(i,h)rep(j,w)
#define rrep(i,m, n) for(int i = m; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define aall(x,n) (x).begin(),(x).begin()+(n)
#define VEC(type,name,n) std::vector<type> name(n);rep(i,n)std::cin >> name[i];
#define pb push_back
#define pf push_front
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define sum accumulate
#define keta fixed<<setprecision
#define vvector(name,typ,m,n,a)vector<vector<typ> > name(m,vector<typ> (n,a))
#define vvvector(name,t,l,m,n,a) vector<vector<vector<t> > > name(l, vector<vector<t> >(m, vector<int>(n,a)));
typedef long long ll;
const int INF = 2000000000;
const long INF64 = 1000000000000000ll;
const ll MOD = 1000000007LL;
typedef unsigned int uint;

int main(){
  int n,m;
  std::cin >> n>>m;
  std::vector<int> k(m);
  std::vector<std::vector<int>> s(m),ss(n);
  rep(i,m){
    std::cin >> k[i];
    rep(j,k[i]){
      int dum;
      std::cin >> dum;
      s[i].pb(dum-1);
      ss[dum-1].pb(i);
    }
  }
  std::vector<int> p(m);
  rep(i,m)std::cin >> p[i];
  int ans=0;
  for(int bit=0;bit<(1<<n);bit++){
    std::vector<int> pp(m);
    //rep(i,m)pp[i]=p[i];
    rep(i,n){
      if(bit&(1<<i)){
        rep(j,ss[i].size())pp[ss[i][j]]++;
      }
    }
    bool han=1;
    rep(i,m){
      if(pp[i]%2!=p[i])han=0;
    }
    if(han)ans++;
  }
  std::cout << ans << std::endl;
}

Measured memory_bytes: 256
#include<stdio.h>

typedef unsigned long long int ulli;

int main(void)
{
	ulli N, K;
	scanf("%lld %lld", &N, &K);
	ulli i=N/K;
	if (i*K+K/2 >= N) {
		printf("%lld", N - i* K);
	}
	else {
		printf("%lld", (i+1) * K - N);
	}

	return 0;
}

Measured memory_bytes: 128
import java.util.*;
class Main{
	public static void main(String[] args){
		Scanner sc =new Scanner(System.in);
		double d = sc.nextDouble();
		double t = sc.nextDouble();
		double s = sc.nextDouble();

		if((d/s) > t){
			System.out.println("No");
		}else{
			System.out.println("Yes");
		}
	}
}

Measured memory_bytes: 28692
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>

using namespace std;

struct Info{
	Info(){
		team_id = correct_num = penalty = 0;
	}
	int team_id,correct_num,penalty;
};

void func(int T,int P, int R){
	Info info[T];
	for(int i = 0; i < T; i++)info[i].team_id = i+1;

	int pena_table[T+1][P+1];
	for(int i = 1; i <= T; i++){
		for(int k = 1; k <= P; k++)pena_table[i][k] = 0;
	}

	int tID,pID,time;
	char message[10];

	for(int loop = 0; loop < R; loop++){
		scanf("%d %d %d %s",&tID,&pID,&time,message);

		if(message[0] == 'C'){
			info[tID-1].correct_num++;
			info[tID-1].penalty += 1200*pena_table[tID][pID] + time;
		}else{
			pena_table[tID][pID]++;
		}
	}

	for(int i = 1; i <= T-1; i++){
		for(int k = T-1; k >= i; k--){
			if(info[k].correct_num > info[k-1].correct_num)swap(info[k],info[k-1]);
			else if(info[k].correct_num == info[k-1].correct_num && info[k].penalty < info[k-1].penalty)swap(info[k],info[k-1]);
			else if(info[k].correct_num == info[k-1].correct_num && info[k].penalty == info[k-1].penalty
					&&info[k].team_id < info[k-1].team_id)swap(info[k],info[k-1]);
		}
	}

	for(int i = 0; i < T; i++){
		printf("%d %d %d\n",info[i].team_id,info[i].correct_num,info[i].penalty);
	}
}

int main(){

	int T,P,R;

	while(true){
		scanf("%d %d %d",&T,&P,&R);
		if(T == 0 && P == 0&& R == 0)break;

		func(T,P,R);
	}

    return 0;
}

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

#define      pb    push_back
#define      ff    first
#define      ss    second
#define      ll    long long int
#define      endl  "\n"
#define      FASTIO        ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);


#define      TEST    int t ; cin >> t ; while( t -- )

const ll big = 10e10 + 11 ;

int  main (  ) {

    FASTIO ;

    vector < int > v ;

    int a , b , c ;
    cin >> a >> b >> c ;

    v.pb( a ) ;
    v.pb( b ) ;
    v.pb( c ) ;

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

    if( v[ 0 ] == v[ 1 ] && v[ 1 ] != v[ 2 ] ){
        cout << "Yes" ;
    }
    else if(  v[ 0 ] != v[ 1 ] && v[ 1 ] == v[ 2 ] ){
          cout << "Yes" ;
    }
    else   cout << "No" ;

    return  0 ;
}



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

int ans, n;
std::string str;
std::map<std::string, bool> hav;

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    std::cin >> str;
    if (!hav[str]) {
      ans++;
      hav[str] = 1;
    }
  }
  printf("%d\n", ans);  
  return 0;  
}

Measured memory_bytes: 19384
#include<iostream>
using namespace std;
int GCD(int a,int b,int c)
{
	int i,t=1;
	for(i=2;i<=a;i++)
	{
		if(a%i==0&&b%i==0&&c%i==0)
		t=i;
	}
	return t;
}
int main()
{
	int k,i,j,l,m=0;
	cin>>k;
	for(i=1;i<=k;i++)
	{
		for(j=1;j<=k;j++)
		{
			for(l=1;l<=k;l++)
			{
				m+=GCD(i,j,l);
			}
		}
	}
	cout<<m;
}

Measured memory_bytes: 3636
#include <stdio.h>

int main(void) {
	int a;
	scanf("%d",&a);
	float N[a];
	for(int i=0;i<a;i++){
		scanf("%f",&N[i]);
	}
	float tmp;
	for(int i=0;i<a;i++){
		for(int j=i+1;j<a;j++){
			if(N[i]<N[j]){
				tmp = N[j];
				N[j] = N[i];
				N[i] = tmp;
			}
		}
	}
	for(int i=a-2;i>=0;i--){
		N[i] = (N[i]+N[i+1])/2;
	}
	printf("%f",N[0]);
	
	return 0;
}

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

#define ull unsigned long long int
#define ll long long
#define vi vector<int>
#define mii map<int,int>
#define all(x) x.begin(),x.end()
#define endl "\n"
#define pb push_back
#define MOD 1e9+7
#define INF 0x3f3f3f3f

using namespace std;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};

int main()
{
 ll A, B; cin >> A >> B;
    char C; cin >> C;
    int D; cin >> D;
    B *= 100; B += D;
    ll X = A*B; X /= 100;
    cout << X << endl;
}


Measured memory_bytes: 3604
#include <functional>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <iomanip>
#include <utility>
#include <cstdlib>
#include <sstream>
#include <bitset>
#include <vector>
#include <cstdio>
#include <ctime>
#include <queue>
#include <deque>
#include <cmath>
#include <stack>
#include <list>
#include <map>
#include <set>

using namespace std;

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

#define dump(x)  cerr << #x << " = " << (x) << endl
#define rep(i,n) for(int i=0;i<(n);i++)
#define ALL(a)  (a).begin(),(a).end()
#define PB push_back
#define sz size()

const double EPS = 1e-10;
const int INF = 100000000;

bool is(string s){
    bool a=false,b=false,c=false;
    if(s.sz<6)return false;
    rep(i,s.sz){
        if('0'<=s[i] && s[i]<='9')a=true;
        if('A'<=s[i] && s[i]<='Z')b=true;
        if('a'<=s[i] && s[i]<='z')c=true;
    }
    if(!a || !b || !c)return false;

    return true;
}
int main(){
    string i;
    cin>>i;
    if(is(i))cout<<"VALID"<<endl;
    else cout<<"INVALID"<<endl;
    
    
    return 0;
}

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

// clang-format off
#define  range(i, l, r) for (int i = (int)(l); i < (int)(r); ++(i))
#define rrange(i, l, r) for (int i = (int)(r) - 1; i >= (int)(l); --(i))

#define  whole(f, x, ...) ([&](decltype((x)) container) { return (f)(  begin(container),  end(container), ## __VA_ARGS__); })(x)
#define rwhole(f, x, ...) ([&](decltype((x)) container) { return (f)( rbegin(container), rend(container), ## __VA_ARGS__); })(x)

#define debug(x) cerr << "(" << __LINE__ << ")" << #x << ": " << (x) << endl

using int32 = int;
using int64 = long long;

const int   mod   = 1e9 + 7;
const int32 inf   = 1001001001;
const int64 infll = 1001001001001001001ll;

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

struct IoSetup { IoSetup(){ cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); cerr << fixed << setprecision(10); } } iosetup;

template <typename T = int64> T input() { T x; cin >> x; return x; }

template <typename T> ostream &operator<<(ostream &os, vector<T> &v) { range(i, 0, v.size()) { os << v[i] << (i + 1 != v.size() ? " " : ""); } return os; } 
template <typename T> istream &operator>>(istream &is, vector<T> &v) { for (T &in : v) is >> in; return is; }
template <typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p) { os << p.first << " " << p.second; return os; }
template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.first >> p.second; return is; }

template <typename T> vector<T> make_v(size_t a, T b) { return vector<T>(a, b); }
template <typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); }

template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
// clang-format on

void solver() {
  int N = input();
  vector<pair<int, int>> ans;

  if (N & 1) {
    range(i, 1, N + 1) {
      range(j, i + 1, N + 1) {
        if (i + j == N ) continue;
        ans.push_back(make_pair(i, j));
      }
    }
  } else {
    range(i, 1, N + 1) {
      range(j, i + 1, N + 1) {
        if (i + j == N + 1) continue;
        ans.push_back(make_pair(i, j));
      }
    }
  }

  cout << ans.size() << endl;
  for (auto p : ans) cout << p << endl;
}

signed main(int argc, char *argv[]) {
  solver();
}

Measured memory_bytes: 384
N,X,Y,Z=map(int,input().split())
mod=10**9+7
forbit=(1<<(X+Y+Z -1 )) +(1<<(Y+Z -1 ))+(1<<(Z -1 ))
mask = ((1<<(X+Y+Z)) -1)
dp=[[0]*(mask+1) for i in range(N+1)]
dp[0][0]=1
for n in range(1,N+1):
    for i in range(mask+1):
        for k in range(10):
            t=((i <<(k+1)) | 1<<k) & mask
            if (t & forbit) == forbit:
                continue
            dp[n][t]+=dp[n-1][i]
            dp[n][t]%=mod
ans=pow(10,N,mod)
for i in range(mask+1):
    ans-=dp[N][i]
    ans%=mod
print(ans)

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

#define int long long

#define PB push_back
#define PPB pop_back
#define MK make_pair
#define ALL(V) V.begin(), V.end()
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<string, int> psi;
typedef pair<int, pii> pipii;

static const int INF = 1LL << 61;
//static const int MOD = 1000000007;
static const int MAX_N = 200005;

int flg[MAX_N];
int n, m;
vector<int> gedo;

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

    cin >> n >> m;

    for (int i = n; 0 < i; --i) gedo.PB(i);

    for (int i = 0; i < m; ++i) {
        int t;
        cin >> t;
        flg[t];
        gedo.PB(t);
    }

    for (auto it = gedo.rbegin(); it != gedo.rend(); ++it) {
        if (flg[*it]) continue;
        cout << *it << endl;
        flg[*it] = true;
    }

    for (int i = 1; i <= n; ++i) if (!flg[i]) cout << i << endl;
}

Measured memory_bytes: 7080
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<long>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvb = vector<vector<bool>>;
using vvc = vector<vector<char>>;
using vvl = vector<vector<long>>;
using pii = pair<int, int>;
using pil = pair<int, long>;
using pll = pair<long, long>;
#define fix20 cout << fixed << setprecision(20)
#define YES cout << "Yes" << endl
#define NO cout << "No" << endl
#define rep(i,n) for(int i=0; i<(int)(n);i++)
#define REP(i,s,t) for(int i=s; i<t; i++)
#define RNG(i,s,t,u) for(int i=s; i<t; i+=u)
#define MOD 1000000007
#define all(vec) vec.begin(), vec.end()

int main(){
  int n;
  cin >> n;
  vl h(n);
  rep(i,n) cin >> h.at(i);
  vl dp(n+1,0);
  dp[1] = abs(h[1] - h[0]);
  for(int i=2;i<n;i++){
    dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]));
  }
  cout << dp[n-1] << endl;
}

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

int main(){
  int N,K;
  cin>>N>>K;
  
  int sum=1;
  
  for(int i=0;i<N;i++){
    if(sum*2<sum+K){
      sum*=2;
    }
    else{
      sum+=K;
    }
  }

  cout<<sum<<endl;
}

Measured memory_bytes: 256
n,m=map(int,input().split())
s = [0] * m
c = [0] * m
for i in range(m):
    s[i], c[i] = map(int, input().split())
k=["0"]*n
if m==0 and n==1:
    print(0)
elif m==0 and n!=1:
    print(10**(n-1))
else:
    for i in range(m):
        if k[s[i]-1]=="0":
            k[s[i]-1]=c[i]
        elif k[s[i]-1]==c[i]:
            k[s[i]-1]=c[i]
        else:
            print(-1)
            break

    else:
        t=0
        if k[0]=="0":
            k[0]=1
        if k[0]==0 and n==1:
            print(0)
        elif k[0]==0 and n!=1:
            print(-1)
        else:
            for i in range(n):
                t=t+10**(n-1-i)*int(k[i])
            print(t)

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

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf=1e9;
const int64_t inf64=1e18;
const double eps=1e-9;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

void solve(int n,int m){
    vector<string> e(n);
    string ts;
    rep(i,0,n) cin >> e[i];
    rep(i,0,m){
        string t;
        cin >> t;
        ts+=t;
    }

    vector<int> sum_len(1<<n);
    rep(i,0,1<<n){
        rep(j,0,n){
            if(((i>>j)&1)==0) continue;
            sum_len[i]+=e[j].size();
        }
    }

    static bool p[5000][1<<12];
    fill_n((bool*)p,5000*(1<<12),false);
    vector<vector<int>> heads(ts.size());
    rep(i,0,ts.size()) p[i][0]=true;
    rep(i,0,ts.size()){
        rep(j,0,n){
            if(i+e[j].size()>ts.size() or e[j]!=ts.substr(i,e[j].size())) continue;
            p[i][1<<j]=true;
            heads[i].push_back(j);
        }
    }
    int ans=0;
    for(int i=ts.size()-1; i>=0; --i){
        rep(j,1,1<<n){
            if(p[i][j] or i+sum_len[j]>ts.size()) continue;
            for(int k:heads[i]){
                if(((j>>k)&1)==0) continue;
                int i2=i+e[k].size();
                if(p[i2][j&(~(1<<k))]){
                    p[i][j]=true;
                    break;
                }
            }
        }
        if(p[i][(1<<n)-1]) ++ans;
    }
    cout << ans << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(10);
    for(;;){
        int n,m;
        cin >> n >> m;
        if(n==0 and m==0) break;
        solve(n,m);
    }
    return 0;
}

Measured memory_bytes: 23488
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define UNIQUE(v) v.erase(unique(all(v)),v.end());
#define fill(a,x) memset(a,x,sizeof(a))
#define zero(a) fill(a,0)
#define minus(a) fill(a,-1)
#define dbg(x) cout << #x"=" << x << endl

const int INF=INT_MAX/3;
const int LIMIT=100;

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

string s,t;

int main(){
  cin>>s>>t;
  if(s.size()<t.size()){
    cout<<"UNRESTORABLE"<<endl;
    return 0;
  }
  int i,j;
  bool unrestorable=true;
  for(i=s.size()-1;i>=t.size()-1;i--){
    for(j=0;j<t.size();j++){
      if((s[i-j]=='?'||s[i-j]==t[t.size()-1-j])&&j==t.size()-1){
        unrestorable=false;
        break;
      }
      if(s[i-j]=='?'||s[i-j]==t[t.size()-1-j])continue;
      if(s[i-j]!=t[t.size()-1-j])break;
    }
    if(!unrestorable)break;
  }
  if(unrestorable){
    cout<<"UNRESTORABLE"<<endl;
    return 0;
  }
  rep(k,t.size())s[i-k]=t[t.size()-1-k];
  rep(k,s.size()){
    if(s[k]=='?')s[k]='a';
  }
  cout<<s<<endl;
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int a,b,c,temp;
    scanf("%d%d%d",&a,&b,&c);
    temp=a;
    a=c;
    c=b;
    b=temp;
    printf("%d %d %d\n",a,b,c);
    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <bitset>
#include <functional>
using namespace std;

typedef long long ll;

ll dp[53][3000];

int main() {
	ll n, a; cin >> n >> a;
	ll x[53];
	for (ll i = 0; i < n; ++i) cin >> x[i];
	dp[0][0] = 1;
	for (ll i = 0; i < n; ++i) {
		for (ll j = n; j >= 1; --j) {
			for (ll k = x[i]; k < 3000; ++k) {
				dp[j][k] += dp[j - 1][k - x[i]];
			}
		}
	}
	for (ll i = 0; i < n; ++i) {

	}
	ll ans = 0;
	for (ll i = 1; i <= n; ++i) {
		ans += dp[i][a*i];
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int N;
    cin >> N;
    int count = N;
    ll ans = 1;
    for (int i = 1; i <= count; i++)
    {
        ans *= i ;
        if(ans >= 1000000007){
            ans %= 1000000007;
        }
    }
    cout << ans << endl;
    

}


Measured memory_bytes: 256
# coding: utf-8
# Your code here!

n = int(input())
hl = list(map(int,input().split()))	
nl = []
before_h = hl[0]
for h in hl:
    if h > before_h:
        nl.append(h-1)
        before_h = h-1
    else:
        nl.append(h)
        before_h = h
if nl == sorted(nl):
    print("Yes")
else:
    print("No")
    
    

Measured memory_bytes: 65176
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (ll i = a; i < b; i++)
#define REP(i,b) FOR(i,0,b)
#define RFOR(i,a,b) for (ll i = a-1; i >= b; i--)
#define RREP(i,a) RFOR(i,a,0)
#define REPALL(i,x) for (ll i = 0; i < x.size(); i++)
#define RREPALL(i,x) for (ll i = x.size()-1; i >= 0; i--)
#define REPITR(itr,x) for (auto itr = (x).begin(); itr != (x).end(); itr++)
#define ALL(x) (x).begin(), (x).end()
#define SORT(x) sort(ALL(x))
#define MIN_ELEMENT(x) min_element(ALL(x))
#define MAX_ELEMENT(x) max_element(ALL(x))
#define COUNT(x,num) count(ALL(x), num)
#define MEMSET(x,val) memset(x, val, sizeof(x))
#define MAX(a,b) a = max(a,b)
#define MIN(a,b) a = min(a,b)
#define debug(x) cerr<<__LINE__<<": "<<(#x)<<" = "<<(x)<<endl;
void YES(bool flag) {cout<<(flag ? "YES" : "NO")<<endl;}
void Yes(bool flag) {cout<<(flag ? "Yes" : "No")<<endl;}
void yes(bool flag) {cout<<(flag ? "yes" : "no")<<endl;}
#define e1 first
#define e2 second
#define nextline putchar('\n')
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef vector<ll> VLL;
typedef vector<vector<ll>> VVLL;
const int INF = 1e7;
const ll MOD = 1e9 + 7;
const double pi = 3.141592653589793;

vector<pair<ll, ll>> factorization_vector(ll n)
{
    vector<pair<ll, ll>> rtn;

    ll m = n;
    ll idx = 0;
    for (ll i = 2; i * i <= m; i++) {
        if (n % i != 0)
            continue;

        rtn.push_back({i,0});
        while (m % i == 0) {
            rtn[idx].second++;
            m /= i;
        }
        idx++;
    }
    if (m != 1) {
        rtn.push_back({m,1});
    }

    return rtn;
}

int main()
{
    ll n, cnt = 0;
    cin>>n;
    vector<pair<ll, ll>> pnum = factorization_vector(n);
    REPALL(i,pnum) {
        int t = pnum[i].second;
        FOR(j,1,t+1) {
            t -= j;
            cnt++;
        }
    }

    //cnt += (int)(n != 1);

    cout<<cnt<<endl;

    return 0;
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
 
#define int long long
 
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
 
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}
 
int N;
int A[111111];
 
int a[111111];
 
signed main(){
    cin>>N;
    string s;cin>>s;
    rep(i,s.size()){
        A[i]=s[i]=='x';
    }
 
    rep(i,2)rep(j,2){
        a[0]=i;a[1]=j;
        for(int j=1;j<N+1;j++){
            a[j+1]=a[j-1]^A[j%N]^a[j];
        }
 
        if(a[0]==a[N]&&a[1]==a[N+1]){
            rep(k,N){
                if(a[k])s[k]='W';
                else s[k]='S';
            }
            cout<<s<<endl;
            return 0;
        }
    }
 
    cout<<-1<<endl;
}

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

using namespace std;

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

    int sum = 0;
    vector<int> s(N);
    for (int i = 0; i < N; i++) {
        cin >> s[i];
        sum += s[i];
    }
    sort(s.begin(), s.end());

    if (sum % 10 == 0) {
        for (int si: s) {
            if (si % 10 > 0) {
                cout << sum - si << endl;
                return 0;
            }
        }
        cout << 0 << endl;
    } else {
        cout << sum << endl;
    }
    return 0;
};


Measured memory_bytes: 256
n = input()
a = [int(x) for x in input().strip().split()]
count = {}
for x in a:
    if x not in count:
        count[x] = 0
    count[x] += 1
sort_keys = sorted(list(count.keys()), reverse=True)

result = 0
position = []
for idx, current in enumerate(sort_keys):
    value = count[current]
    if idx == 0:
        result += current * (value - 1)
        position.append([current, value])
    else:
        new_pos = 0
        while len(position) > 0 and value > 0:
            if position[0][1] > value:
                result += position[0][0] * value
                new_pos += value * 2
                position[0][1] -= value
                value = 0
            else:
                result += position[0][1] * position[0][0]
                new_pos += position[0][1] * 2
                value -= position[0][1]
                position.remove(position[0])
        if value > 0:
            new_pos += value
            result += current * value
        position.append([current, new_pos])
print(result)


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

using namespace std;
using ll = long long;
using ii = pair<ll, ll>;

const vector<ii> xs {
    { 0, 0 },
    { 20, 18 },
    { 11, 9 },
    { 4, 3 },
    { 13, 9 },
    { 14, 9 },
    { 5, 3 },
    { 16, 9 },
    { 17, 9 },
    { 2, 1 },
}; 

ll solve(const vector<ii>& ds)
{
    ll ans = 0;
    stack<ll> rs;

    for (auto p : ds)
    {
        auto d = p.first;
        auto c = p.second;

        if (d == 0)
        {
            ans += c;
            continue;
        }

        auto qtd = xs[d].first;
        auto n = xs[d].second;
        auto k = c / n;
        auto r = c % n;

        if (r == 0)
        {
            r = n;
            --k;
        }
//cout << "qtd = " << qtd << ", k = " << k << ", r = " << r << ", d = " << d << '\n';
        ans += qtd * k;

        while (r--)
            rs.push(d);
    }

    while (rs.size() > 1)
    {
        auto x = rs.top();
        rs.pop();
 
        auto y = rs.top();
        rs.pop();

        auto z = x + y;

        if (z > 9)
        {
            rs.push(z / 10);
            rs.push(z % 10);
        } else
            rs.push(z);

        ++ans;
    } 

    return ans;
}

int main()
{
    ios::sync_with_stdio(false);

    int M;
    cin >> M;

    vector<ii> ds(M);

    for (int i = 0; i < M; ++i)
    {
        ll d, c;
        cin >> d >> c;

        ds[i] = ii(d, c);
    }

    auto ans = solve(ds);

    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 9856
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE BinaryLiterals #-}
{-# LANGUAGE MultiWayIf #-}
{-# LANGUAGE NumDecimals #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TupleSections #-}

import Control.Applicative
import Control.Arrow
import Control.Monad
import Control.Monad.ST

import Data.Char
import Data.List
import Data.Maybe

import qualified Data.ByteString.Char8 as B

import Data.Array.ST.Safe
import Data.STRef

import Debug.Trace
import Text.Printf

readInt = readLn :: IO Int
readInteger = readLn :: IO Integer
readInts = map ( fst . fromJust . B.readInt ) . B.words <$> B.getLine
readIntegers = map ( fst . fromJust . B.readInteger ) . B.words <$> B.getLine

which a b f = if f then a else b
mp [ a, b ] = ( a, b )

modifyArray a i f = writeArray a i =<< f <$> readArray a i

main = readInteger >>= print . fizzbuzz

fizzbuzz 0 = 0
fizzbuzz k
	| k `mod` 3 /= 0 && k `mod` 5 /= 0 = k + fizzbuzz ( pred k )
	| otherwise = fizzbuzz $ pred k

Measured memory_bytes: 24184
from collections import deque

n,m=map(int,input().split())

edges=[[] for _ in range(n)]#[[１番目の部屋からいける部屋],[２番目の部屋からいける部屋]...]

for _ in range(m):
    a,b=map(int,input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

todo=deque([[0,0]])
seen=[-1]*n
seen[0]=0

while todo:
    node,parent=todo.popleft()#現在探索している部屋、その親
    
    for to in edges[node]:
        if seen[to]!=-1:
            continue

        todo.append([to,node])
        seen[to]=node

print('Yes')

for parent in seen[1:]:
    print(parent+1)

Measured memory_bytes: 39640
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
// const ll INF = 1e18;
# define rep(i, n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
# define reps(i, n) for(ll i=1, i##_len=(n); i<=i##_len; ++i)
# define rrep(i, n) for(ll i=((int)(n)-1); i>=0; --i)
# define rreps(i, n) for(ll i=((int)(n)); i>0; --i)
# define all(x) (x).begin(), (x).end()

ll N;

int Main() {
    cin >> N;
    ll sum = 0;
    reps(i, N) {
        reps(j, N) {
            reps(k, N) {
                sum += gcd(i,gcd(j,k));
            }
        }
    }
    
    cout << sum << endl;
    
    return 0;
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


Measured memory_bytes: 3572
# include "cstdio"
# include "iostream"

using namespace std;

const int maxm=1e5+10;

int N;
long long A[maxm],B[maxm],C[maxm],DP[maxm][3],Ans;

int main(){
	register int i;
	scanf("%d",&N);
	for(i=1;i<=N;i++) scanf("%lld%lld%lld",A+i,B+i,C+i);
	for(i=1;i<=N;i++){
		DP[i][0]=max(DP[i-1][1]+A[i],DP[i-1][2]+A[i]);
		DP[i][1]=max(DP[i-1][0]+B[i],DP[i-1][2]+B[i]);
		DP[i][2]=max(DP[i-1][0]+C[i],DP[i-1][1]+C[i]);
	}
	Ans=max(DP[N][0],max(DP[N][1],DP[N][2]));
	printf("%lld",Ans);
	return 0;
}

Measured memory_bytes: 4992
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())
#define ll long long
#define pb(a) push_back(a)
#define MOD 1000000007
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

typedef vector<unsigned int>vec;
typedef vector<vec> mat;
//typedef tuple<ll, ll, ll> T;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

void add(ll& a, ll b){a = (a+b) % MOD;}

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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    vector<int> a(n);
    REP(i,n)cin>>a[i];
    int ans=0;
    REP(i,n){
        if((i+1)==a[a[i]-1]&&i<a[i]) ans++;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 640
parseInt(x) = parse(Int, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function root(uf::Array{Int,1},x)
	s=x
	while uf[s]>0
		s=uf[s]
	end
	s
end
function same(uf::Array{Int,1},x,y)
	root(uf,x)==root(uf,y)?true:false
end
function unite(uf::Array{Int,1},x,y)
	l = root(uf,x)
	r = root(uf,y)
	if l < r
		uf[l] += uf[r]
		uf[r] = l
	elseif l > r
		uf[r] += uf[l]
		uf[l] = r
	end
end

function eval(a::Tuple{Int,Int},b::Tuple{Int,Int})
	if a[2]<b[2]
		1
	elseif a[2]==b[2]
		0
	else
		-1
	end
end

function hpush(h::Array{Tuple{Int,Int},1},x::Tuple{Int,Int})
	push!(h,x)
	if length(h) > 1
		l = length(h)
		k = l>>1
		while eval(x,h[k])==1&&k>=1
			tmp = h[k]
			h[k] = x
			h[l] = tmp
			k = max(k>>1,1)
			l = l>>1
		end
	end
end

function hpop(h::Array{Tuple{Int,Int},1})
	x = h[1]
	z = pop!(h)
	if !isempty(h)
		h[1] = z
		k = 1
		l = length(h)
		while k <= l
			if 2*k>l
				break
			elseif 2*k+1>l
				if eval(h[2*k],z)>=0
					break
				else
					tmp = h[2*k]
					h[2*k] = z
					h[k] = tmp
					k = 2*k
				end
			else
				if eval(z,h[2*k])>=0&&eval(z,h[2*k+1])>=0
					break
				else
					t = eval(h[2*k],h[2*k+1])>=0?2*k:2*k+1
					tmp = h[t]
					h[t] = z
					h[k] = tmp
					k = t
				end
			end
		end
	end
	x
end

function main()
	n,gu,gv = readline() |> split |> parseMap
	e = [Int[] for i in 1:n]
	el = zeros(Int,n-1,2)
	for i in 1:n-1
		a,b = readline() |> split |> parseMap
		push!(e[a],b)
		push!(e[b],a)
		el[i,:] = [a,b]
	end
	dis = -ones(Int,n)
	h = Array{Tuple{Int,Int},1}()
	push!(h,(gv,0))
	while !isempty(h)
		v,w = hpop(h)
		dis[v] = dis[v]<0?w:min(dis[v],w)
		for i in 1:length(e[v])
			if dis[e[v][i]]<0　|| dis[e[v][i]]>w+1
				dis[e[v][i]] = w+1
				hpush(h,(e[v][i],w+1))
			end
		end
	end
	hunt = dis[gu]>>1
	ng = [Int[] for i in 1:n]
	for i in 1:n-1
		if dis[el[i,1]]>hunt&&dis[el[i,2]]>hunt
			push!(ng[el[i,1]],el[i,2])
			push!(ng[el[i,2]],el[i,1])
		end
	end
	disu = -ones(Int,n)
	h = Array{Tuple{Int,Int},1}()
	push!(h,(gu,0))
	while !isempty(h)
		v,w = hpop(h)
		disu[v] = disu[v]<0?w:min(disu[v],w)
		for i in 1:length(ng[v])
			if disu[ng[v][i]]<0　|| disu[ng[v][i]]>w+1
				disu[ng[v][i]] = w+1
				hpush(h,(ng[v][i],w+1))
			end
		end
	end
	ep = 0
	ev = 0
	for i in 1:n
		if disu[i]>-1&&dis[i]>ev
			ep = i
			ev = dis[i]
		end
	end
	z = disu[ep]
	println(ev-1)
end

main()

Measured memory_bytes: 221768
#include <bits/stdc++.h>
using namespace std;
int n;
long long p1,p2;
vector<pair<int,int> > v;
long long mx,mn=0x3f3f3f3f3f3f3f3f,x[200001],y[200001];
long long ans=0x3f3f3f3f3f3f3f3f;
int main() {
    cin>>n;
    for (int i=0; i<n; i++) {
        cin>>p1>>p2;
        mx=max(mx,p1); mn=min(mn,p1);
        mx=max(mx,p2); mn=min(mn,p2);
        if (p1>p2) swap(p1,p2);
        v.push_back({p1,p2});
    }
    sort(v.begin(),v.end());
    for (int i=0; i<n; i++) {x[i]=v[i].first; y[i]=v[i].second;}
    long long mnr=x[0],mxr=x[n-1],mnb=0x3f3f3f3f3f3f3f3f,mxb=0;
    for (int i=0; i<n; i++) {
        mnb=min(mnb,y[i]); mxb=max(mxb,y[i]);
    }
    ans=min(ans,(mxr-mnr)*(mxb-mnb));
    multiset<long long> s;
    for (int i=0; i<n; i++) s.insert(x[i]);
    ans=min(ans,(mx-mn)*((*prev(s.end()))-(*s.begin())));
    for (int i=0; i<n; i++) {
        s.erase(s.find(x[i]));
        s.insert(y[i]);
        ans=min(ans,(mx-mn)*((*prev(s.end()))-(*s.begin())));
    }
    cout<<ans<<'\n';
}
/*
7
1 5
1 6
2 3
3 9
5 6
7 7
7 8
*/

Measured memory_bytes: 17208
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)n; i++)
#define rep1(i, n) for (ll i = 1; i <= (ll)n; i++)
#define PI 3.14159265358979323846
#define vll vector<long long>
#define vvll vector<vector<long long>>
#define pll pair<long long, long long>
using namespace std;
using ll = long long;
using ld = long double;

// ----本問について----
// 問題：Polygon - Area
// 問題文URL：https://onlinejudge.u-aizu.ac.jp/problems/CGL_3_A
// 所要時間：
// 学んだこと：
// ------------------

// ----ここから本問のソースコード----

// グローバル変数（入力）
ll n;
vector<complex<ld>> cord;

// 入力
void input() {
  cin >> n;
  cord.resize(n);
  rep(i,n){
    ld x,y;
    cin >> x >> y;
    cord[i]=complex<ld>(x,y);
  }
}

ld cross_product(complex<ld> a, complex<ld> b) { return (conj(a) * b).imag(); }

void solve() {
  cout << fixed << setprecision(1);
  rep1(i, n-1) { cord[i] -= cord[0]; }
  cord[0]-=cord[0];
  ld ans = 0.0;
  rep1(i, n - 2) { ans += cross_product(cord[i], cord[i + 1])/2.0; }
  cout << ans << endl;
}

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



Measured memory_bytes: 3288
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll MOD = 1000000007;
const int IINF = INT_MAX;
const ll LLINF = LLONG_MAX;
const int MAX_N = int(50 + 5);
const double EPS = 1e-10;
const int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define SORT(v) sort((v).begin(), (v).end())
#define ALL(v) (v).begin(), (v).end()

ll n, k, h, w, d;
ll X1[MAX_N], X2[MAX_N], Y1[MAX_N], Y2[MAX_N], D1[MAX_N], D2[MAX_N];
ll field[MAX_N*2][MAX_N*2][MAX_N*2];
vector<ll> xs, ys, ds, xunzip, yunzip, dunzip;
map<ll,ll> xzip, yzip, dzip;

void compress(vector<ll> &x, map<ll, ll> &zip, vector<ll> &unzip) {
    sort(x.begin(), x.end());
    x.erase(unique(x.begin(), x.end()), x.end());
    unzip.resize(x.size());
    for (int i = 0; i < x.size(); i++) {
        zip[x[i]] = i;
        unzip[i] = x[i];
    }
}

int main() {
    cin >> n >> k;
    REP(i,n){
        cin >> X1[i] >> Y1[i] >> D1[i] >> X2[i] >> Y2[i] >> D2[i];
        xs.push_back(X1[i]);
        xs.push_back(X2[i]);
        ys.push_back(Y1[i]);
        ys.push_back(Y2[i]);
        ds.push_back(D1[i]);
        ds.push_back(D2[i]);
    }

    compress(xs, xzip, xunzip);
    compress(ys, yzip, yunzip);
    compress(ds, dzip, dunzip);

    w = xzip.size();
    h = yzip.size();
    d = dzip.size();

    REP(i,n){
        field[yzip[Y1[i]]][xzip[X1[i]]][dzip[D1[i]]]++;
        field[yzip[Y1[i]]][xzip[X2[i]]][dzip[D1[i]]]--;
        field[yzip[Y2[i]]][xzip[X1[i]]][dzip[D1[i]]]--;
        field[yzip[Y2[i]]][xzip[X2[i]]][dzip[D1[i]]]++;
        field[yzip[Y1[i]]][xzip[X1[i]]][dzip[D2[i]]]--;
        field[yzip[Y1[i]]][xzip[X2[i]]][dzip[D2[i]]]++;
        field[yzip[Y2[i]]][xzip[X1[i]]][dzip[D2[i]]]++;
        field[yzip[Y2[i]]][xzip[X2[i]]][dzip[D2[i]]]--;
    }
    REP(i,h+1)REP(j,w)REP(m,d){
        field[i][j+1][m] += field[i][j][m];
    }
    REP(j,w+1)REP(i,h)REP(m,d){
        field[i+1][j][m] += field[i][j][m];
    }
    REP(m,d+1)REP(i,h)REP(j,w){
        field[i][j][m+1] += field[i][j][m]; 
    }
    ll ans = 0;
    REP(i,h)REP(j,w)REP(m,d){
        if(field[i][j][m]>=k) 
            ans += (yunzip[i+1]-yunzip[i])*(xunzip[j+1]-xunzip[j])*(dunzip[m+1]-dunzip[m]);
    }
    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 12360
/*input
2
2
2
100
*/
#include <bits/stdc++.h>
using namespace std;

long long int arr[1123456],brr[1123456];
int main(){
    int x,a,b,c, ans = 0;
    cin>>a>>b>>c>>x;
    x /= 50;
    for(int i=0;i<=a;i++){
        for(int j=0;j<=b;j++){
            for(int k=0;k<=c;k++){
                if(10*i+2*j+k==x)ans++;
            }
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int m = scan.nextInt();
		int l = scan.nextInt();

		// ?????? A ??\???
		int[][] A;
		A = new int[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				A[i][j] = scan.nextInt();
			}
		}
		// ?????? B ??\???
		int[][] B;
		B = new int[m][l];
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < l; j++) {
				B[i][j] = scan.nextInt();
			}
		}

		// ?????? C ??\???
		// long ?????????
		long[][] C;
		C = new long[n][l];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < l; j++) {
				for (int k = 0; k < m; k++) {
					C[i][j] = C[i][j] + A[i][k] * B[k][j];
				}
			}
		}

		// ?????? C ??????
		for (int i = 0; i < n; i++) {

			// C[i][0]???1???????????????????????????for(" " + C[i][j])?????????
			int j = 0;
			System.out.print(C[i][j]);
			// ?????????C[i][1]??????
			for (j = 1; j < l; j++) {
				System.out.print(" " + C[i][j]);
			}
			System.out.println();
		}

	}

}

Measured memory_bytes: 54104
#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 pair<ll,ll> pii;
typedef vector<int> VI; typedef vector<ll> VL;
const int MD = (int)1e9 + 7;
void dbg(){ cerr << "\n"; }  template <typename T,typename ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }


int main(){
	//cin.tie(0); ios_base::sync_with_stdio(false);
	int n;
	cin >>n;
	map<int, int> mp;
	rep(i, n){
		int z; cin >>z;
		mp[-z]++;
	}
	
	ll bf =-1,  ans =0;
	for(auto x: mp){
		if(x.second < 2) continue;
		if(bf==-1 && x.second >=4){
			ans = (ll)x.first * x.first;
			break;
		}else if(bf !=-1){
			ans = (ll)x.first * bf;
			break;
		}
		bf = x.first;
	}
	
	cout << ans <<"\n";
	return 0;
}

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

int main() {
	int n;
	cin >> n;
	int dp[45];
	dp[0] = 1;
	dp[1] = 1;
	for (int i = 2;i <= n;i++) {
		dp[i] = dp[i - 1] + dp[i - 2];
	}
	cout << dp[n] << endl;

	return 0;
}


Measured memory_bytes: 3100
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAX = 510000;
const ll mod = 1000000007;

ll fac[MAX], finv[MAX], inv[MAX];

void COMinit(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i=2;i<MAX;i++){
        fac[i] = fac[i-1] * i % mod;
        inv[i] = mod - inv[mod%i] * (mod / i) % mod;
        finv[i] = finv[i-1] * inv[i] % mod;
    }
}
ll COM(int n, int k){
    if(n<k) return 0;
    if(n<0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod;
}

int main(){
    
    int n, k;
    cin >> n >> k;
    vector<ll> a(n);
    for(int i=0;i<n;i++)cin >> a[i];
    sort(a.begin(), a.end());
    
    COMinit();

    ll nyan = 0;

    for(int i=0;i<n;i++){
        nyan += -a[i] * COM(n-i-1,k-1) % mod + a[i] * COM(i,k-1) % mod;
        nyan %= mod;
    }
    cout << nyan;
}

Measured memory_bytes: 12928
class Cube:
    def __init__(self, u, s, e, w, n, d):
        self.u = u
        self.s = s
        self.e = e
        self.w = w
        self.n = n
        self.d = d

    def rotate(self, dic):
        if dic == "N":
            tmp = self.u
            self.u = self.s
            self.s = self.d
            self.d = self.n
            self.n = tmp
        elif dic == "E":
            tmp = self.u
            self.u = self.w
            self.w = self.d
            self.d = self.e
            self.e = tmp
        elif dic == "W":
            tmp = self.u
            self.u = self.e
            self.e = self.d
            self.d = self.w
            self.w = tmp
        else:
            tmp = self.u
            self.u = self.n
            self.n = self.d
            self.d = self.s
            self.s = tmp


def main():
    u, s, e, w, n, d = map(int, input().split())
    O = input()

    cube = Cube(u, s, e, w, n, d)
    for i in range(len(O)):
        cube.rotate(O[i])
    print(cube.u)


if __name__ == '__main__':
    main()


Measured memory_bytes: 5608
#include <iostream>
#include <vector>
#include <cstdio>
#include <string>
#include <algorithm>
#include <map>
#include <numeric>
using namespace std;


vector< vector <int> > a(2 * 100000 + 1);
vector<long long int> tmpRes(2 * 100000 + 1, 0);
vector<long long int> res(2 * 100000 + 1, 0);

void dfs(int before, int idx, long long int now)
{
    long long int score = tmpRes[idx];
    res[idx] = now + score;
    if (a[idx].empty()) {
        return ;
    }
    for (int j = 0; j < a[idx].size(); j++) {
        if (a[idx][j] == before) {
            continue;
        }
        dfs(idx, a[idx][j], now + score);
    }
}

int main()
{
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n - 1; i++) {
        int ta, tb;
        cin >> ta >> tb;
        a[ta].push_back(tb);
        a[tb].push_back(ta);
    }

    for (int i = 0; i < q; i++) {
        int p, x;
        cin >> p >> x;
        tmpRes[p] += x;
    }

    dfs(0, 1, 0);

    for (int i = 1; i < n + 1; i++) {
        cout << res[i] << ' ';
    }
    cout << endl;
}



Measured memory_bytes: 25856
#include <iostream>
#include <vector>

int main() {
    int A, B, C;
    std::string S = "";
    std::cin >> A >> B >> C;

    if ( ( A != B && A == C) || ( A == B && A != C ) || ( B != C && B == A) || ( B == C && B != A) ) {
        S = "Yes";
    } else {
        S = "No";
    }

    std::cout << S << std::endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main() {
    while (true) {
        int w, h;
        cin >> w >> h;
    
        if (w==0 && h==0) {
            break;
        }
    
        int xs, ys;
        cin >> xs >> ys;
        xs -= 1;
        ys -= 1;
        
        int xg, yg;
        cin >> xg >> yg;
        xg -= 1;
        yg -= 1;
    
        int S[h][w];
    
        for (int i=0; i<h; i++) {
            for (int j=0; j<w; j++) {
                S[i][j] = -1;
            }
        }
    
        int n;
        cin >> n;
        
        for (int i=0; i<n; i++) {
            int ci, di, xi, yi;
            cin >> ci >> di >> xi >> yi;
            xi -= 1;
            yi -= 1;
            
            if (di==0) {
                for (int i=yi; i<yi+2; i++) {
                    for (int j=xi; j<xi+4; j++) {
                        S[i][j] = ci;
                    }
                }
            }
            else {
                for (int i=yi; i<yi+4; i++) {
                    for (int j=xi; j<xi+2; j++) {
                        S[i][j] = ci;
                    }
                }
            }
        }
        
        if (S[ys][xs]==-1) {
            cout << "NG" << endl;
            continue;
        }
        
        int visited[h][w];
        
        for (int i=0; i<h; i++) {
            for (int j=0; j<w; j++) {
                visited[i][j] = 0;
            }
        }
        
        queue<P> q;
        q.push(P(ys, xs));
        visited[ys][xs] = 1;
        
        while (q.size()) {
            P p = q.front();
            q.pop();
            int cy = p.first;
            int cx = p.second;
            
            for (int i=0; i<4; i++) {
                int ny = cy+dy[i];
                int nx = cx+dx[i];
                
                if (!(0<=ny && ny<h && 0<=nx && nx<w)) {
                    continue;
                }
                
                if (visited[ny][nx]==0 && S[ny][nx]==S[cy][cx]) {
                    q.push(P(ny, nx));
                    visited[ny][nx] = 1;
                }
            }
        }
        
        if (visited[yg][xg]==1) {
            cout << "OK" << endl;
        }
        else {
            cout << "NG" << endl;
        }
    }
}


Measured memory_bytes: 3104
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();
vector<int> f(vector<int> arr) { // val, freq, freq2
    unordered_map<int, int> cnt;
    for(int num: arr)
        cnt[num] += 1;
    cnt[INT_MAX] = 0;
    multimap<int, int> cnt2;
    for(auto& p: cnt) {
        cnt2.insert({arr.size()-p.second, p.first});
    }
    // sort(cnt2.begin(), cnt2.end());
    return {cnt2.begin()->second, cnt2.begin()->first, next(cnt2.begin())->first};

}
int main() {
    int n;
    cin >> n;
    vector<int> arr(n, 0);
    vector<vector<int>> arr2(2, vector<int>());
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
        arr2[i%2].push_back(arr[i]);
    }
    vector<int> v1 = f(arr2[0]);
    vector<int> v2 = f(arr2[1]);
    if (v1[0] != v2[0])
        cout << v1[1] + v2[1] << endl;
    else
        cout << min(v1[2]+v2[1], v1[1]+v2[2]) << endl;

    return 0;
}



Measured memory_bytes: 5664
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int k, n;
    cin >> k >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a.at(i);
    }
    int minimum = k - (a.at(1) - a.at(0));
    for (int i = 0; i < n - 1; i++) {
        int minlength;
        if (i == 0) {
            minlength = a.at(n - 1) - a.at(0);
        } else {
            minlength = min(k - (a.at(i + 1) - a.at(i)), k - (a.at(i) - a.at(i - 1)));
        }
        minimum = min(minimum, minlength);
    }

    cout << minimum << endl;
}

Measured memory_bytes: 1024
#include<vector>
#include<list>
#include<algorithm>
#include<iostream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
int main(){
  int i,j;
  int a[50],n;
  while(cin>>n&&n){
    for(i=0;i<n;i++)
      cin>>a[i];
    i=0;
    for(j=i;j<n-1&&a[j]+1==a[j+1];j++);
    if(i==j)
      cout<<a[i];
    else
      cout<<a[i]<<"-"<<a[j];
    for(i=j+1;i<n;i=j+1){
      for(j=i;j<n-1&&a[j]+1==a[j+1];j++);
      if(i==j)
	cout<<" "<<a[i];
      else
	cout<<" "<<a[i]<<"-"<<a[j];
    }
    cout<<endl;
  }
  return 0;
}

Measured memory_bytes: 0
#!/usr/bin/env python
# -*- coding: utf-8 -*-


import sys


def partition(A, p, r):
    x = A[r]
    i = p - 1
    assert p <= r
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return dict(array=A, cursor=i + 1)


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(int, _input[1].split()))
    assert len(array) == array_length
    raw_result = partition(A=array, p=0, r=array_length - 1)
    array_result, cursor = raw_result['array'], raw_result['cursor']
    array_result[cursor] = '[' + str(array_result[cursor]) + ']'
    print(*array_result)

Measured memory_bytes: 18240
let rec solve pairs ans (arr: int []) =
    match pairs with
    | [] -> ans
    | (a, b) :: pairs -> if arr.[a] < arr.[b] then solve pairs ("Yes" :: ans) arr else solve pairs ("No" :: ans) arr

let [| n; k |] =
    stdin.ReadLine().Split(" ") |> Array.map int

let pair =
    [ for x in [ k .. (n - 1) ] do
        (x - k, x) ]


stdin.ReadLine().Split(" ")
|> Array.map int
|> solve pair []
|> List.rev
|> String.concat "\n"
|> printfn "%s"


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


int main() {
    int h,w;
    cin>>h>>w;
    int cost=0;
    char m[h][w];
    int dist[h][w];
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            cin>>m[i][j];
            dist[i][j]=1<<9;
            if(m[i][j]=='.')cost++;
        }
    }
    dist[0][0]=1;
    queue<int> x;
    queue<int> y;
    x.push(0);
    y.push(0);
    int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
    while(x.size()){
        //cout<<x.front()<<" "<<y.front()<<endl;
        for (int i = 0; i < 4; ++i) {
            int xx=x.front()+dx[i],yy=y.front()+dy[i];
            if(xx<0 || yy<0 ||xx>=h||yy>=w)continue;
            if(m[xx][yy]=='.' && dist[xx][yy]>=1<<9){
                dist[xx][yy]=dist[x.front()][y.front()]+1;
                x.push(xx);
                y.push(yy);
            }
        }
        x.pop();
        y.pop();
    }
    if(dist[h-1][w-1]<1<<9){
        cout<<cost-dist[h-1][w-1]<<endl;
    }
    else cout<<-1<<endl;
    return 0;
}

Measured memory_bytes: 256