akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int l;
		for(l=1; l<N; l++){
			N -= l;
		}
		if(N != l){
			System.out.println("No");
			System.out.flush();
			return;
		}
		System.out.println("Yes");
		System.out.println(l+1);
		int[][] answer = new int[l+1][l];
		int Index = 1;
		for(int i=0; i<=l; i++){
			System.out.print(l);
			int j=0;
			for(; j<i; j++){
				System.out.print(" "+answer[j][i-1]);
			}
			for(; j<l; j++){
				System.out.print(" "+(answer[i][j]=Index++));
			}
			System.out.println("");
		}
		System.out.flush();
		return;
	}

}


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

const int maxn = 8e5;
int n, m, tot, val[maxn + 5], ch[maxn + 5][3], cnt, res[maxn + 5];
bool sal[maxn + 5];
char s[maxn + 5];

int dfs(int k, int t, int s) {
	int x = ++tot;
	if (!k) return val[x] = s, x;
	ch[x][0] = dfs(k - 1, t * 3, s);
	ch[x][1] = dfs(k - 1, t * 3, s + t);
	ch[x][2] = dfs(k - 1, t * 3, s + t * 2);
	return x;
}

void salsa(int x) {
	sal[x] ^= 1, swap(ch[x][1], ch[x][2]);
}

void push_down(int x) {
	if (sal[x]) {
		rep(i, 0, 2) salsa(ch[x][i]);
		sal[x] = false;
	}
}

void rumba(int x) {
	if (!ch[x][0]) return;
	push_down(x);
	int t = ch[x][0];
	ch[x][0] = ch[x][2];
	ch[x][2] = ch[x][1];
	ch[x][1] = t;
	rumba(ch[x][0]);
}

void work(int x, int t, int s) {
	if (!ch[x][0]) {
		res[val[x]] = s, cnt++;
		return;
	}
	push_down(x);
	rep(i, 0, 2) work(ch[x][i], t * 3, s + i * t);
}

int main() {
	scanf("%d %s", &n, s + 1);
	m = strlen(s + 1);
	dfs(n, 1, 0);
	rep(i, 1, m) {
		if (s[i] == 'S') salsa(1);
		else rumba(1);
	}
	work(1, 1, 0);
	rep(i, 0, cnt - 1) printf("%d%c", res[i], " \n"[i == cnt - 1]);
	return 0;
}

Measured memory_bytes: 19512
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

int main(void)
{
	int a, b;

	cin >> a >> b;

	if (a + b >= 10)
	{
		cout << "error" << endl;
	}
	else
	{
		cout << a + b << endl;
	}
	return 0;
}

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

int main() {

  long long int n, m, d;
  cin >> n >> m >> d;

  long double ans = m - 1;
  ans /= n;
  if ( d > 0 ) {
    ans *= ( n - d ) * 2;
    ans /= n;
  }

  cout << fixed << setprecision(10) << ans << endl;

  return 0;

}


Measured memory_bytes: 256
#include <cstdio>
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <cmath>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#define rep(i,n) for (int i=0;i<n;i++)
using ll = long long;
using namespace std;

void solve(){

}
int main (){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,t;
    cin >> n >> t;
    vector<pair<int,int>> a(n);
    rep(i,n){
        int m,k;
        cin >> m >> k;
        a[i] = {m,k};
    }
    bool frag = false ;
    int q = 1000;
    rep(i,n){
        if(a[i].second<=t){
            frag = true;
            q = min(q,a[i].first);
        }
    }
    if(frag){
        cout << q;
    }
    else{
        cout << "TLE";
    }


    return 0;
}

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

struct ABC{
    int p, a, b, c;  // p = a - b
};


vector<long long> calc_score(int head, int tail, int total, const vector<pair<int, int>> & ac){
    priority_queue<int> pq;
    vector<long long> score(total + 1, 0);
    for (int i = 0; i != head; ++i){
        score[i + 1] = score[i] + ac[i].first;
        pq.push(ac[i].second - ac[i].first);
    }
    for (int i = head; i != tail; ++i){
        int s = ac[i].second - ac[i].first;
        int t = pq.top();
        if (t > s){
            pq.pop();
            pq.push(s);
            score[i + 1] = score[i] + t + ac[i].first;
        }else{
            score[i + 1] = score[i] + ac[i].second;
        }
    }
    return score;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int X, Y, Z;
    cin >> X >> Y >> Z;
    int XYZ = X + Y + Z;
    vector<ABC> abc(XYZ);
    for (auto & item : abc) {
        cin >> item.a >> item.b >> item.c;
        item.p = item.a - item.b;
    }
    sort(abc.begin(), abc.end(), [](ABC lhs, ABC rhs){ return lhs.p > rhs.p;});
//    for (auto & item : abc){
//        cout << item.p << ' ' << item.a << ' ' << item.b << ' ' << item.c << endl;
//    }
    vector<pair<int, int>> ac(XYZ);
    vector<pair<int, int>> bc(XYZ);
    for (int i = 0; i != XYZ; ++i){
        ac[i] = make_pair(abc[i].a, abc[i].c);
        bc[i] = make_pair(abc[i].b, abc[i].c);
    }
    reverse(bc.begin(), bc.end());
    auto scoreL = calc_score(X, X + Z, XYZ, ac);
    auto scoreR = calc_score(Y, Y + Z, XYZ, bc);
    long long record = 0;
    for (int k = X; k <= X + Z; ++k){
        long long score = scoreL[k] + scoreR[XYZ - k];
        record = max(record, score);
    }
    cout << record << endl;
    return 0;
}



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

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for (ll(i) = (m); (i) < (n); ++(i))
#define REP(i, n) FOR(i, n, 0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll)1e15;

pll A[100005];

ll T[100005];

int main()
{
    int N, M;
    cin >> N >> M;
    REP(i, M)
    {
        cin >> A[i].first >> A[i].second;
        T[A[i].first - 1]++;
        T[A[i].second]--;
    }
    FOR(i, N, 1)
    {
        T[i] += T[i - 1];
    }

    int ans = 0;
    REP(i, N)
    {
        if (T[i] == M)
            ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 2560
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <stack>
#include <vector>
using namespace std;
typedef long long ll;

ll size[51];
ll p[51];

ll dfs(ll level,ll num){
  if(num == 0)return 0;
  else if(num == size[level])return p[level];
  else if(num >= size[level-1] + 2){
    return dfs(level-1,num-size[level-1] - 2) + p[level-1] + 1;
  }
  else if(num >= 1){
    return dfs(level-1,num-1);
  }
}

int main(){
  size[0] = 1;
  p[0] = 1;
  for(int i = 1;i <= 50;i++){
    size[i] = size[i-1] * 2 + 3;
    p[i] = p[i-1] * 2 + 1;
  }

  ll n,x;
  cin >> n >> x;

  ll ans = dfs(n,x);

  cout << ans << endl;
}

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

using namespace std;

int main(){
	int a,b,c,k;
	scanf("%d%d%d%d",&a,&b,&c,&k);
	if(a>c){
		swap(a,c); 
	}
	if(b>c){
		swap(b,c); 
	}
	printf("%d",a+b+(1<<k)*c); 
	return 0; 
} 

Measured memory_bytes: 256
n, c, k = map(int, input().split())
t = []
for i in range(n):
    t.append(int(input()))
t.sort()
ans = 0
counter = 0
lim = t[0]
for i in range(n):
    if counter < c and (t[i] - lim) <= k:
        counter += 1
    else:
        counter = 1
        lim = t[i]
        ans += 1
print(ans + 1)

Measured memory_bytes: 13336
#include<bits/stdc++.h>
   using namespace std;
   int main()
   {
      string s,p;
      cin>>s>>p;

      int n=s.size();
      int m=p.size();

      int dp[n+1][m+1];
      memset(dp,0,sizeof(dp));


      for(int i=1;i<=n;i++)
      {
         for(int j=1;j<=m;j++)
         {
            if(s[i-1]==p[j-1])
            {
               dp[i][j]=dp[i-1][j-1]+1;
            }
            else
            {
               dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
         }
      }

      vector<char> l;
   // l.push_back()
      int i=n,j=m;
      while(i>0 && j>0)
      {
         if(s[i-1]==p[j-1])
         {
            l.push_back(s[i-1]);
            i--;
            j--;
         }
         else
         if(dp[i-1][j] > dp[i][j-1])
         {
            i--;
         }
         else
         j--;
      }
      reverse(l.begin(),l.end());
   for(int i=0;i<l.size();i++)
   {
      cout<<l[i];
   }

   }



Measured memory_bytes: 35456
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <map>
#include <tuple>
#include <vector>
using namespace std;

typedef tuple<int, int, int> point;
#define x(p) get<0>(p)
#define y(p) get<1>(p)
#define z(p) get<2>(p)

inline int r(int &a, int &b) {
	static constexpr int C = ~(1 << 31);
	static constexpr int M = (1 << 16) - 1;

	a = 36969 * (a & M) + (a >> 16);
	b = 18000 * (b & M) + (b >> 16);
	return (C & ((a << 16) + b)) % 1000000;
}

inline bool check(int y, int z, const map<int, int> &contour) {
	const auto it = contour.upper_bound(y);
	return it != contour.end() && it->second < z;
}

int solve(vector<point> &points) {
	sort(points.begin(), points.end());

	int max_count = 0;
	int prev_x = x(points.front());
	vector<tuple<int, int, int>> buf;
	vector<map<int, int>> maps{{{1, -1}}};
	buf.reserve(points.size());
	maps.reserve(points.size());

	for(const auto &p : points) {
		const int x = x(p);
		const int y = -y(p);
		const int z = z(p);

		if(prev_x != x) {
			maps.resize(max_count + 1);
			prev_x = x;

			for(const auto &e : buf) {
				int k, ty, tz;
				tie(k, ty, tz) = e;

				auto &target = maps[k];
				auto it = target.lower_bound(ty);

				if(it == target.end() || it->second > tz) {
					target[ty] = tz;
					it = target.find(ty);

					while(it != target.begin()) {
						--it;
						if(tz > it->second) break;
						it = target.erase(it);
					}
				}
			}
			buf.clear();
		}

		int low = 0;
		int high = maps.size();

		while(low + 1 < high) {
			const int mid = (low + high) / 2;
			if(check(y, z, maps[mid])) {
				low = mid;
			}
			else {
				high = mid;
			}
		}

		if(low == max_count) ++max_count;
		buf.emplace_back(high, y, z);
	}

	return max_count;
}

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

	for(int m, n, a, b; cin >> m >> n >> a >> b && a;) {
		vector<point> points;
		points.reserve(n + m);

		for(int i = 0; i < m; ++i) {
			int x, y, z;
			cin >> x >> y >> z;
			points.emplace_back(x, y, z);
		}

		for(int i = 0; i < n; ++i) {
			const int x = r(a, b);
			const int y = r(a, b);
			const int z = r(a, b);
			points.emplace_back(x, y, z);
		}

		cout << solve(points) << endl;
	}

	return EXIT_SUCCESS;
}

Measured memory_bytes: 12460
#include <cstdio>
#include <vector>
using namespace std;

bool check(const vector<int> &v){
	int d = v[1] - v[0];
	for(int i = 2; i < v.size(); ++i){
		if(v[i] - v[i-1] != d) return false;
	}
	return true;
}

int solve(int n){
	vector<int> h(n + 1), v;
	for(int i = 0; i <= n; ++i){
		scanf("%d", &h[i]);
	}

	for(int i = 0; i <= n; ++i){
		v.assign(h.begin(), h.begin() + i);
		v.insert(v.end(), h.begin() + (i + 1), h.end());
		if(check(v)) return h[i];
	}
	return -1;
}

int main(){
	int n;
	while(scanf("%d", &n), n){
		printf("%d\n", solve(n));
	}
}

Measured memory_bytes: 1052
#include <iostream>
using namespace std;
int main() {
	int sx, sy, tx, ty;
	cin >> sx >> sy >> tx >> ty;
	int dx = tx - sx;
	int dy = ty - sy;
	// Path 1
	cout << string(dy, 'U') << string(dx, 'R');
	// Path 2
	cout << string(dy, 'D') << string(dx, 'L');
	// Path 3
	cout << 'L' << string(dy+1, 'U') << string(dx+1, 'R') << 'D';
	// Path 4
	cout << 'R' << string(dy+1, 'D') << string(dx+1, 'L') << 'U';
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int N;
    cin >> N;
    bool times = false;

    if (N > 81){
        times = false;
    }
    else{
        for (int i = 2;i<10;i++){
        	if (N%i == 0){
            	if (N/i <= 9){
                	times = true;
            	}
        	}

        }
    }
  	if (N == 1){
    	times = true;
    }
  	

    

    if (times == false){
        cout << "No" << endl;
    }
    else{
        cout << "Yes" << endl;
    }
  	
  		
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  int a, b;
  cin >> a >> b;
  
  if(a == 1 && b != 1){
    cout << "Alice" << endl;
  }
  else if(b == 1 && a != 1){
    cout << "Bob" << endl;
  }
  else if(a != 1 && b != 1 && a < b){
     cout << "Bob" << endl;
  }
  else if(a != 1 && b != 1 && a > b){
     cout << "Alice" << endl;
  }
  else if(a == b){
    cout << "Draw" << endl;
  }
    
}

Measured memory_bytes: 3616
def main():
    n = int(input())
    res = 0
    if n<=8:
        for i in range(1,n):
            if n//i == n%i:
                res += i
    else:
        for i in range(1,int(n**(1/2))):
            if (n-i)/i == (n-i)//i and (n-i)//i>0:
                res += (n-i)//i
    print(res)
if __name__ == '__main__':
    main()


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

#define pb push_back
#define ff first
#define ss second

const long long MAXN = 2e5 + 21, inf = 1e18 + 21, LG = 20;

string s[MAXN];
string t;
map <string, int> mp;
int n;
int mx, ind;

int main() {
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);	
    cin >> n;
    for (int i = 0; i < n; i++) {
	cin >> t;
	mp[t]++;
	mx = max(mp[t], mx);
    }

    for (auto y: mp) 
	if (y.ss == mx) 
	    s[ind++] = y.ff;

    sort(s, s + ind);

    for (int i = 0; i < ind; i++)
	cout << s[i] << '\n';
    return 0;
}


Measured memory_bytes: 25472
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]

di = [1, -1, 0, 0, 1, -1, 1, -1]
dj = [0, 0, 1, -1, 1, -1, -1, 1]

for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            continue
        cnt = 0
        for ii, jj in zip(di, dj):
            ni = i + ii
            nj = j + jj
            if 0 <= ni < h and 0 <= nj < w:
                if s[ni][nj] == '#':
                    cnt += 1
        s[i][j] = chr(ord('0') + cnt)

for x in s:
    print(''.join(x))


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

// {U}{INT,LONG,LLONG}_{MAX,MIN}
#define INF         INT_MAX/3
#define LLINF       LLONG_MAX/3
#define MOD         (1000000007LL)
#define MODA(a, b)  a=((a)+(b))%MOD
#define MODP(a, b)  a=((a)*(b))%MOD
#define inc(i, l, r)   for(int i=(l);i<(r);i++)
#define dec(i, l, r)   for(int i=(r)-1;i>=(l);i--)
#define pb          push_back
#define se          second
#define fi          first
#define mset(a, b)  memset(a, b, sizeof(a))

using LL  = long long;
using G   = vector<vector<int>>;

int di[] = {0, -1, 0, 1};
int dj[] = {1, 0, -1, 0};
// }}}

int main() {
    cin.tie(0);ios::sync_with_stdio(false);
    int n;cin >> n;
    vector<int> a;
    a.pb(0);
    inc(i, 0, n){
        int aa;cin >> aa;
        a.pb(aa);
    }
    a.pb(0);
    int sum = 0;
    inc(i, 1, n+2){
        sum += abs(a[i]-a[i-1]);
    }
    inc(i, 1, n+1){
        cout << sum-abs(a[i]-a[i-1])-abs(a[i+1]-a[i])+abs(a[i+1]-a[i-1]) << endl;
    }
    return 0;
}


Measured memory_bytes: 1784
// Created by Tanuj Jain
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pii;
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int INF = 0x3f3f3f3f;
int knight_moves[8][2]={{-2,-1},{-1,-2},{1,-2},{2,-1},{-2,1},{-1,2},{1,2},{2,1}};
int moves[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int main()
{
	ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

	//#ifndef ONLINE_JUDGE
	//freopen("inputf.in","r",stdin);
	//freopen("outputf.in","w",stdout);
	//#endif

	int x1,x2,x3,x4,x5;
	cin>>x1>>x2>>x3>>x4>>x5;
	int sum=x1+x2+x3+x4+x5;
	cout<<15-sum;

	
}

Measured memory_bytes: 3576
#include <bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(ll i=a;i>=b;i--)
#define Max(a,b,c) max(a,max(b,c))
#define Min(a,b,c) min(a,min(b,c))
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define pc(x)  __builtin_popcount (x)
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define ld long double
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod 1000000007
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout) 
#define gcd __gcd
#define primeDEN 727999983
#define nx_pe next_permutation(s.begin(),s.end())
#define cl cout<<"\n"
#define sp(x) setprecision(x)

void solve()
{
    ll k;
    cin>>k;
    ll sum=0;
    ll id=-1;
    for(ll i=1;i<10000000;++i){
        sum=sum*10+7;
        if(sum%k==0){
            id=i;
            break;
        }
        sum%=k;
    }
    cout<<id<<"\n";
}


    
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin) ;
    freopen("ouput.txt", "w", stdout) ;
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL) ; cout.tie(NULL) ;
    std::ios::sync_with_stdio(false);
    ll te=1;
    // cin>>te;
    while(te--){
        solve();
    }
    
}


Measured memory_bytes: 3632
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <bitset>
#include <numeric>
#include <complex>
#include <iomanip>
#include <cassert>
#include <random>


int main() {
    int n; std::cin >> n;
    std::vector<long long> c(n), s(n), f(n);
    for (int i = 0; i < n - 1; i++) std::cin >> c[i] >> s[i] >> f[i];
    for (int t = 0; t < n; t++) {
        long long cur = 0;
        for (int i = t; i < n - 1; i++) {
            cur = std::max(s[i], (cur + f[i] - 1) / f[i] * f[i]) + c[i];
        }
        std::cout << cur << std::endl;
    }
    return 0;
}



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

template <int MOD>
struct ModInt {
    using lint = long long;
    int val;

    // constructor
    ModInt(lint v = 0) : val(v % MOD) {
        if (val < 0) val += MOD;
    };

    // unary operator
    ModInt operator+() const { return ModInt(val); }
    ModInt operator-() const { return ModInt(MOD - val); }
    ModInt inv() const { return this->pow(MOD - 2); }

    // arithmetic
    ModInt operator+(const ModInt& x) const { return ModInt(*this) += x; }
    ModInt operator-(const ModInt& x) const { return ModInt(*this) -= x; }
    ModInt operator*(const ModInt& x) const { return ModInt(*this) *= x; }
    ModInt operator/(const ModInt& x) const { return ModInt(*this) /= x; }
    ModInt pow(lint n) const {
        auto x = ModInt(1);
        auto b = *this;
        while (n > 0) {
            if (n & 1) x *= b;
            n >>= 1;
            b *= b;
        }
        return x;
    }

    // compound assignment
    ModInt& operator+=(const ModInt& x) {
        if ((val += x.val) >= MOD) val -= MOD;
        return *this;
    }
    ModInt& operator-=(const ModInt& x) {
        if ((val -= x.val) < 0) val += MOD;
        return *this;
    }
    ModInt& operator*=(const ModInt& x) {
        val = lint(val) * x.val % MOD;
        return *this;
    }
    ModInt& operator/=(const ModInt& x) { return *this *= x.inv(); }

    // compare
    bool operator==(const ModInt& b) const { return val == b.val; }
    bool operator!=(const ModInt& b) const { return val != b.val; }

    // I/O
    friend std::ostream& operator<<(std::ostream& os, const ModInt& x) noexcept { return os << x.val; }
};

template <class T>
struct Combination {
    int max_n;
    std::vector<T> f, invf;

    explicit Combination(int n)
        : max_n(n), f(n + 1), invf(n + 1) {
        f[0] = 1;
        for (int i = 1; i <= n; ++i) {
            f[i] = f[i - 1] * i;
        }

        invf[max_n] = f[max_n].inv();
        for (int i = max_n - 1; i >= 0; --i) {
            invf[i] = invf[i + 1] * (i + 1);
        }
    }

    T fact(int n) const { return f[n]; }
    T invfact(int n) const { return invf[n]; }
    T perm(int a, int b) const {
        return a < b ? T(0) : f[a] * invf[a - b];
    }
    T comb(int a, int b) const {
        return a < b ? T(0) : f[a] * invf[a - b] * invf[b];
    }
};

constexpr int MOD = 1e9 + 7;
using mint = ModInt<MOD>;

const Combination<mint> C(1000);

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

    mint ans = 0;
    for (int i = 0; i <= k; ++i) {
        ans += mint(-1).pow(k - i) * C.comb(k, i) * mint(i).pow(n);
    }
    std::cout << ans << std::endl;
    return 0;
}



Measured memory_bytes: 3128
package main

import "fmt"

func main() {
	var a, b int
	fmt.Scan(&a, &b)
	if b < 0 {
		if (b-a+1)%2 == 0 {
			fmt.Println("Positive")
		} else {
			fmt.Println("Negative")
		}
	} else if 0 < a {
		fmt.Println("Positive")
	} else {
		fmt.Println("Zero")
	}
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#include <ext/hash_map>
#include <ext/numeric>

using namespace std;
using namespace __gnu_cxx;

#define REP(i,n) for( (i)=0 ; (i)<(n) ; (i)++ )
#define rep(i,x,n) for( (i)=(x) ; (i)<(n) ; (i)++ )
#define REV(i,n) for( (i)=(n) ; (i)>=0 ; (i)-- )
#define FORIT(it,x) for( (it)=(x).begin() ; (it)!=(x).end() ; (it)++ )
#define foreach(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();++it)
#define rforeach(it,c) for(__typeof((c).rbegin()) it=(c).rbegin();it!=(c).rend();++it)
#define foreach2d(i, j, v) foreach(i,v) foreach(j,*i)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define SZ(x) ((int)(x).size())
#define MMS(x,n) memset(x,n,sizeof(x))
#define mms(x,n,s) memset(x,n,sizeof(x)*s)
#define pb push_back
#define mp make_pair
#define NX next_permutation
#define UN(x) sort(all(x)),x.erase(unique(all(x)),x.end())
#define CV(x,n) count(all(x),(n))
#define FIND(x,n) find(all(x),(n))-(x).begin()
#define ACC(x) accumulate(all(x),0)
#define PPC(x) __builtin_popcountll(x)
#define LZ(x) __builtin_clz(x)
#define TZ(x) __builtin_ctz(x)
#define mxe(x) *max_element(all(x))
#define mne(x) *min_element(all(x))
#define low(x,i) lower_bound(all(x),i)
#define upp(x,i) upper_bound(all(x),i)
#define NXPOW2(x) (1ll << ((int)log2(x)+1))
#define PR(x) cout << #x << " = " << (x) << endl ;

typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef pair<int, int> pii;

const int OO = (int) 2e9;
const double eps = 1e-9;

const int N = 100005;

int n, k;
long long sum[100][3];
int main() {
    int num[100];
    cin>>n>>k;
    sum[0][0]=1;
    sum[0][1]=0;
    for(int i=1;i<=n;i++){
        cin>>num[i];
        num[i]%=2;
       // sum[i][num[i]]=1;
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=1;j++){
            sum[i][j]+=(sum[i-1][j]+sum[i-1][(j+num[i])%2]);
        }
    }
    cout<<sum[n][k]<<endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
 
class Main {
	int w;
	int h;
	int n;
	int[] x;
	int[] y;
	int[] a;
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		Main m = new Main(sc);
		m.solve();
		sc.close();
	}
	Main(Scanner sc){
		w = sc.nextInt();
		h = sc.nextInt();
		n = sc.nextInt();
		x = new int[n];
		y = new int[n];
		a = new int[n];
		for(int i=0;i<n;i++){
			x[i] = sc.nextInt();
			y[i] = sc.nextInt();
			a[i] = sc.nextInt();
		}
	}
	void solve(){
		boolean[][] xy = new boolean[h][w];
		for(int i=0;i<n;i++){
			switch(a[i]){
				case 1:
					for(int j=0;j<x[i];j++){
						for(int k=0;k<h;k++){
							xy[k][j] = true;
						}
					}
					break;
				case 2:
					for(int j=x[i];j<w;j++){
						for(int k=0;k<h;k++){
							xy[k][j] = true;
						}
					}
					break;
				case 3:
					for(int j=0;j<y[i];j++){
						for(int k=0;k<w;k++){
							xy[j][k] = true;
						}
					}
					break;
				case 4:
					for(int j=y[i];j<h;j++){
						for(int k=0;k<w;k++){
							xy[j][k] = true;
						}
					}
					break;
			}
		}
		int cnt = 0;
		for(int i=0;i<w;i++){
			for(int j=0;j<h;j++){
				if(!xy[j][i]) cnt++;
			}
		}
		System.out.println(cnt);
	}
}

Measured memory_bytes: 22356
#include <iostream>
#include <vector>
#include <map>
#include <climits>
#include <algorithm>
using namespace std;

int main()
{
    int n, m; cin >> n >> m;
    int p, q;
    vector<int> currentCards(n);
    map<int, int> cards;

    for(int i = 0; i < n; i++)
    {
        cin >> currentCards[i];
    }
    sort(currentCards.begin(), currentCards.end());

    for(int i = 0; i < m; i++)
    {
        cin >> p >> q;
        if(cards.count(q))
        {
            cards[q] = cards[q] + p;
        }
        else
        {
            cards[q] = p;
        }
    }

    int pointer = 0;
    for (map<int, int>::reverse_iterator it = cards.rbegin(); it != cards.rend() && pointer < n; it++)
    {
        int val = it->first, count = it->second;
        for(int i = 0; i < count && pointer < n; i++)
        {
            if(currentCards[pointer] < val)
            {
                currentCards[pointer] = val;
            }
            else
            {
                pointer = n;
            }
            pointer++;
        }
    }

    long long res = 0;
    for(int i = 0; i < n; i++)
    {
        res = res + currentCards[i];
    }
    cout << res << endl;

    return 0;
}

Measured memory_bytes: 5376
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<numeric>
using namespace std;
#define INF (1 << 30) - 1
#define LINF 1LL << 60
const int MOD = 1000000007;
using ll = long long;
using P = pair<int, int>;

struct Edge {
    long long to;
};
using Graph = vector<vector<Edge>>;
 
struct LCA {
    vector<vector<int>> parent; 
    vector<int> dist;           
    LCA(const Graph &G, int root = 0) { init(G, root); }
 
    void init(const Graph &G, int root = 0) {
        int V = G.size();
        int K = 1;
        while ((1 << K) < V) K++;
        parent.assign(K, vector<int>(V, -1));
        dist.assign(V, -1);
        dfs(G, root, -1, 0);
        for (int k = 0; k + 1 < K; k++) {
            for (int v = 0; v < V; v++) {
                if (parent[k][v] < 0) {
                    parent[k + 1][v] = -1;
                } else {
                    parent[k + 1][v] = parent[k][parent[k][v]];
                }
            }
        }
    }
 
    void dfs(const Graph &G, int v, int p, int d) {
        parent[0][v] = p;
        dist[v] = d;
        for (auto e : G[v]) {
            if (e.to != p) dfs(G, e.to, v, d + 1);
        }
    }
 
    int query(int u, int v) {
        if (dist[u] < dist[v]) swap(u, v); 
        int K = parent.size();
        for (int k = 0; k < K; k++) {
            if ((dist[u] - dist[v]) >> k & 1) {
                u = parent[k][u];
            }
        }
        if (u == v) return u;
        for (int k = K - 1; k >= 0; k--) {
            if (parent[k][u] != parent[k][v]) {
                u = parent[k][u];
                v = parent[k][v];
            }
        }
        return parent[0][u];
    }

    int get_dist(int u, int v){
        return dist[u] + dist[v] - 2 * dist[query(u, v)];
    }

    bool is_on_path(int u, int v, int a){
        return get_dist(u, a) + get_dist(a, v) == get_dist(u, v);
    }
};

Graph g;

int main(){
    int n, q;
    cin >> n;
    g.resize(n);
    for(int i = 0; i < n; ++i){
        int k;
        cin >> k;
        for(int j = 0; j < k; ++j){
            int c;
            cin >> c;
            g[i].push_back({c});
        }
    }

    LCA lca(g, 0);
    cin >> q;
    for(int i = 0; i < q; ++i){
        int u, v;
        cin >> u >> v;
        cout << lca.query(u, v) << endl;
    }
    return 0;
}


Measured memory_bytes: 18992
/*

    Bismillahirrahmanirrahim
	If you want something you never had, you must be willing to do what you have never done.

*/
                                          
#include <bits/stdc++.h>

#define st first
#define nd second
#define B begin()
#define E end()
#define sz size()
#define pb push_back
#define mp make_pair 
#define respa return 0

using namespace std;
typedef long long ll;

const int N = 1e6 + 17, mod = 1e9 + 7;

int tt = 1, n, b[N];
bool u[N];

void solve () {
	scanf("%d", &n);
	vector <int> v, ans;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &b[i]);
		v.pb(b[i]);
	}
	reverse(v.B, v.E);
	while (!v.empty()) {
		bool ok = 0;
		for (int i = 0; i < v.sz; i++) {
			if (v[i] == v.sz - i) {
				ok = 1;
				ans.pb(v[i]);
				v.erase(v.B + i);
				break;
			}
		}
		if (!ok) {
			printf("-1");
			return;
		}
	}
	reverse(ans.B, ans.E);
	for (auto i : ans) {
		printf("%d \n", i);
	}
}

int main () {
	// scanf("%d", &tt);
	while (tt--) solve();
	respa;
}


Measured memory_bytes: 256
n,x=map(int,input().split())
p=sorted(list(map(int,input().split())))
def gcd(a,b):
  if a<b:
    a,b=b,a
  while a%b>0:
    a,b=b,a%b
  return b
ans=abs(x-p[0])
for i in range(1,n):
  ans=gcd(ans,p[i]-p[i-1])
  
print(ans)

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

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


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

void output_array(vector<int> &v)
{
  for (int i = 0; i < v.size(); i++)
    cout << (i ? " " : "") << v[i];
  cout << "\n";
}

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

  int n;
  cin >> n;
  vector<int> x(n);
  for (int i = 0; i < n; i++)
    cin >> x[i];

  output_array(x);

  for (int i = 1; i < n; i++)
  {
    int v = x[i];
    int j;
    for (j = i - 1; j >= 0 && x[j] > v; j--)
    {
      x[j + 1] = x[j];
    }
    x[j + 1] = v;
    output_array(x);
  }

  return 0;
}



Measured memory_bytes: 3176
import java.util.*;
public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder(sc.next());
		StringBuilder sb1 = new StringBuilder("");
		StringBuilder sb2 = new StringBuilder("");
		int Q = Integer.parseInt(sc.next());
		boolean order = true;
		for(int i = 0; i < Q; i++) {
			int T = Integer.parseInt(sc.next());
			if(T == 1) {
				order = !order;
			} else {
				int f = Integer.parseInt(sc.next());
				if(f == 1) {
					boolean temp_order = !order;
					if(temp_order) {
						sb2.append(sc.next());
					} else {
						sb1.append(sc.next());
					}
				} else {
					if(order) {
						sb2.append(sc.next());
					} else {
						sb1.append(sc.next());
					}
				}
			}
		}
		StringBuilder ans = new StringBuilder(sb1.reverse().append(sb.append(sb2)));
		if(order) {
			System.out.println(ans);
		} else {
			System.out.println(ans.reverse());
		}
	}
}


Measured memory_bytes: 89208
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#define F first
#define S second
#define PII pair<LL, LL>
typedef long long LL;

using namespace std;

LL n;

int main() {
  //ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  for (int i = 111; i <= 999; i += 111) {
    if (i >= n)
      return cout << i, 0;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define all(x) x.begin(),x.end()
#define let auto const

template<typename... Types>
struct dynarr: std::vector<Types...> {
  using std::vector<Types...>::vector;
  using size_type = typename std::vector<Types...>::size_type;
  auto&& operator[](size_type i) { return this->at(i); }
  auto&& operator[](size_type i) const { return this->at(i); }
};

int main() {
  i64 N;
  cin >> N;
  cout << N * N * N << endl;
}


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

int main() {
  int n;
  cin >> n;
  vector<int> h(n);
  for (int i = 0; i < n; i++) cin >> h.at(i);
  int longest = 0, current = 0;
  for (int i = 1; i < n; i++) {
    if (h.at(i) <= h.at(i - 1)) {
      current++;
    } else {
      longest = max(longest, current);
      current = 0;
    }
  }
  longest = max(longest, current);
  cout << longest << endl;
}

Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <map>
#include <set>
#include <stack>
#include <queue>
 
using namespace std;
 
#define pb(n)	push_back(n)
#define mp(n,m) make_pair(n,m)
#define fi 	first
#define se 	second
#define all(r) (r).begin(),(r).end()
 
#define REP(i,s,e)	for(int i=(s); i<(e); i++)
#define rep(i,n)	REP(i,0,n)
#define REPE(i,s,e)	for(int i=s; i>e; i--)
#define repe(i,n)	REPE(i,n,-1)


typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
typedef vector<vi> vvi;
 
const int IMAX=((1<<30)-1)*2+1;
const int INF=100000000;
const double EPS=1e-10;
//int mod=1000000007
 


int main(){
	int n;
	int c[6]={500,100,50,10,5,1};
	while(cin >>n && n >0){
		n=1000-n;
		int a=0;
		rep(i,6){
			a+=n/c[i];
			n%=c[i];
		}
		cout<<a<<endl;
	}
}

Measured memory_bytes: 1156
/*input
6 15
6 5
5 6
6 4
6 6
3 5
7 2
*/

// One day you'll leave this world behind... 
// So, live a life you'll remember...

//code author: iamxlr8

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

#define ll long long
#define endl "\n"
#define pb push_back
#define all(c) c.begin(),c.end()
#define hell 1000000007
#define inf 100000000000001
#define F first
#define S second
#define off ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

ll fun(ll pos,ll W,vector<ll>&v,vector<ll>&w,vector<vector<ll>>&dp){
	if(pos==v.size() or W==0) return 0;
	if(dp[pos][W]!=-1) return dp[pos][W];
	ll ans=fun(pos+1,W,v,w,dp);
	if(W-w[pos]>=0)
		ans=max(ans,v[pos]+fun(pos+1,W-w[pos],v,w,dp));
	return dp[pos][W]=ans;
}

void solve(){
	ll n,W;
	cin>>n>>W;
	vector<ll>v(n),w(n);
	for(ll i=0;i<n;i++)
		cin>>w[i]>>v[i];
	vector<vector<ll>>dp(n+1,vector<ll>(W+1,-1));
	cout<<fun(0,W,v,w,dp);
}

int main(){
    off;
    ll tests=1;
    // cin>>tests;
    ll tno=1;
    while(tests--){
        // cout<<"Case "<<tno++<<": ";
        solve();
        // cout<<endl;
    }
    return 0;
}

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


int main() {

	vector<int> result;
	while (true)
	{
		
		int n;
		int a[50000];
		cin >> n;
		if (n == 0) {
			break;
		}
		for (int i = 0; i < n; i++) {
			cin >> a[i];
		}

		sort(a, a + n);
		int res = 1000000000;
		for (int i = 0; i < n - 1; i++) {
			if (res > a[i + 1] - a[i]) {
				res = a[i + 1] - a[i];
			}
		}
		result.push_back(res);
		
	}	

	for (int i = 0; i < result.size(); i++)
	{
		cout << result[i] << endl;
	}

}

Measured memory_bytes: 3152
#include<cstdio>
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<queue>
using  ll = long long;
using namespace std;

int main(){
  int n; cin >> n;
  ll a[n+1];
  ll temp = 0;
  ll total = 0;
  for(int i = 0; i < n; i++){
    cin >> temp;
    total += temp;
    a[i] = total;    
  }

  a[n] = 0;
  sort(a, a+n+1);
  temp = 1;
  ll ans = 0;

  for(int i = 1; i < n+1; i++){
    if(a[i] == a[i-1]){
      temp++;
    } else {
      ans += temp*(temp-1)/2;
      temp = 1;
    }
  }
  ans += temp*(temp - 1)/2;
  cout << ans << endl;
}


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

class direction{
public:
	int x, y, turn;
	direction(int newx, int newy){
		x = newx;
		y = newy;
	}
};

int main()
{
	int w, h, wall[31][31][4], gone[31][31], turn[31][31], x, y, t, input, before;
	char str[31];
	while (cin >> w >> h, (w || h)){
		//初期化
		for (int i = 0; i < 31; i++){
			for (int j = 0; j < 31; j++){
				for (int k = 0; k < 4; k++){
					wall[i][j][k] = -1;
				}
				gone[i][j] = 0;
				turn[i][j] = -1;
			}
		}
		//外枠
		for (int i = 0; i < w; i++){
			wall[i][0][0] = 1; //上辺
			wall[i][h - 1][2] = 1; //下辺
		}
		for (int i = 0; i < h; i++){
			wall[0][i][1] = 1; //左辺
			wall[w - 1][i][3] = 1; //右辺
		}

		//入力による壁の設定
		for (int i = 0; i < h; i++){
			for (int j = 0; j < w - 1; j++){
				cin >> input;
				wall[j][i][3] = input; //右に行けるか
				wall[j + 1][i][1] = input; //左に行けるか
			}
			if (i < h - 1){
				for (int j = 0; j < w; j++){
					cin >> input;
					wall[j][i][2] = input; //下に行けるか
					if (i < h - 1)
						wall[j][i + 1][0] = input; //上に行けるか
				}
			}
		}

		queue<direction> q;
		direction d = direction(0, 0);
		turn[0][0] = 1;
		gone[0][0] = 1;
		q.push(d);
		while (gone[w - 1][h - 1] != 1 && q.size()>0){
			x = q.front().x;
			y = q.front().y;
			t = turn[x][y];
			if (wall[x][y][0] == 0 && gone[x][y - 1] == 0){
				direction d = direction(x, y - 1);
				q.push(d);
				gone[x][y - 1] = 1;
				turn[x][y - 1] = t + 1;
			}
			if (wall[x][y][1] == 0 && gone[x - 1][y] == 0){
				direction d = direction(x - 1, y);
				q.push(d);
				gone[x - 1][y] = 1;
				turn[x - 1][y] = t + 1;
			}
			if (wall[x][y][2] == 0 && gone[x][y + 1] == 0){
				direction d = direction(x, y + 1);
				q.push(d);
				gone[x][y + 1] = 1;
				turn[x][y + 1] = t + 1;
			}
			if (wall[x][y][3] == 0 && gone[x + 1][y] == 0){
				direction d = direction(x + 1, y);
				q.push(d);
				gone[x + 1][y] = 1;
				turn[x + 1][y] = t + 1;
			}
			q.pop();
		}
		if (turn[w - 1][h - 1] == -1)
			cout << 0 << endl;
		else
			cout << turn[w - 1][h - 1] << endl;
	}
	return 0;
}

Measured memory_bytes: 1236
#include <iostream>

int main(){
	std::string S;
	int N,K;
	std::cin>>N>>S>>K;

	char muta = S[K-1];

	for(int i=0;i<N;++i){
		if(S[i] != muta){
			S[i] = '*';
		}
	}
	std::cout<<S;
	return 0;
}


Measured memory_bytes: 888
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int a, b;
    cin >> a >> b;
    if (a < b) {
        cout << "a < b" << endl;
    } else if (a > b){
        cout << "a > b" << endl;
    } else if (a == b){
        cout << "a == b" << endl;
    }
}

Measured memory_bytes: 3104
n=[True]*100001
n[0]=n[1]=False
for i in range(2,317):
  if n[i]:
    for j in range(i**2,100000,i):
      n[j]=False
c=[0]*100002
for i in range(3,100001):
  c[i]=c[i]+c[i-1]
  if i%2==1 and n[i] and n[int((i+1)/2)]:
    c[i]=c[i]+1
for i in range(int(input())):
  a=input().split(' ')
  print(c[int(a[1])]-c[int(a[0])-1])

Measured memory_bytes: 8916
// In the name of god
#include <bits/stdc++.h>
using namespace std;
long long int a,b,c,d;
int main(){
	cin>>a>>b;
	for(int i=0;i<b;i++){
		cin>>c;
		d+=c;
	}
	if(d<a){
		cout<<"No";
	}
	else{
		cout<<"Yes";
	}
}


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

#define p(x) (x)*(x)

int round(int x)
{
  if(x > 255) return 255;
  else if(x < 0) return 0;
  else return x;
}

int main()
{
  while(1){
    int N, M;
    cin >> N >> M;
    if(N == 0 && M == 0) break;
    int C[M], x[N];
    for(int i = 0; i < M; i++)
      cin >> C[i];
    for(int i = 0; i < N; i++)
      cin >> x[i];
    int a[256];
    fill(a,a+256,INT_MAX);
    for(int i = 0; i < M; i++){
      int n = round(128+C[i]);
      a[n] = p(n-x[0]);
    }
    int b[256];
    for(int t = 1; t < N; t++){
      fill(b,b+256,INT_MAX);
      for(int i = 0; i < 256; i++){
        if(a[i] == INT_MAX) continue;
        for(int j = 0; j < M; j++){
          int n = round(i+C[j]);
          b[n] = min(b[n],a[i]+p(n-x[t]));
        }
      }
      copy(b,b+256,a);
    }
    cout << *min_element(a,a+256) << endl;
  }
}

Measured memory_bytes: 1236
import java.util.*;
import java.util.ArrayList;
import java.util.Collections;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int l = sc.nextInt();
        String[] S = new String[n];
        for(int i = 0; i < n; i++){
            S[i] = sc.next();
        }
        Arrays.sort(S);
        for(int i = 0; i < n; i++){
            System.out.print(S[i]);
        }
    }
}

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

import qualified Data.ByteString.Char8 as B
import Data.Maybe (fromJust)
readInt = fst . fromJust . B.readInt
readInts = map (fst . fromJust . B.readInt) . B.words <$> B.getLine :: IO [Int]
read2dInts = map (map (fst . fromJust . B.readInt) . B.words) . B.lines <$> B.getContents

main :: IO ()
main = do
  (x:y:z:k:_) <- fmap (map read . words) getLine :: IO [Int]
  as <- readInts
  bs <- readInts
  cs <- readInts
  -- mapM_ print $ naive k as bs cs
  -- mapM_ print $ solve x y z k (sort as) (sort bs) (sort cs)
  mapM_ print $ solve x y z k as bs cs

solve x y z k as bs cs = comp (comp (takek as) (takek bs)) $ takek cs
  --comp (takek cs) $ comp (takek as) (takek bs)
  where
    takek = take k . reverse . sort
    naive'' k as bs = takek [ a + b | a <- as, b <- bs ]

    comp as bs = go [] as bs
      where
        go cs _ [] = cs
        go cs as (b:bs) = go (take k . merge cs $ map (+b) as) as bs

    merge :: (Ord a) => [a] -> [a] -> [a]
    merge as [] = as
    merge [] bs = bs
    merge (a:as) (b:bs)
      | a >= b = a:(merge as (b:bs))
      | a < b  = b:(merge (a:as) bs)
      
    naive' k as bs = takek $ do
      a <- as 
      b <- bs 
      return $ a + b


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

int main() {
	int n, m;
	cin >> n >> m;
	vector<ll> a(n), b(n);
	vector<pair<ll, ll>> v(n);
	rep(i, n) {
		cin >> a[i] >> b[i];
		v[i] = make_pair(a[i], b[i]);
	}
	sort(v.begin(), v.end());
	ll ans = 0;
	rep(i, n) {
		if (v[i].second < m) {
			ans += v[i].first * v[i].second;
			m -= v[i].second;
		}
		else {
			ans += v[i].first * m;
			cout << ans << endl;
			return 0;
		}
	}
}

Measured memory_bytes: 3328
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline

def resolve():
    N = int(inp())

    S = 0
    D = 0
    for i in range(N):
        d, c = map(int, inp().split())
        S += d*c
        D += c

    print((D-1) + (S-1)//9)

if __name__ == "__main__":
    resolve()

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
ll GetDigit(ll num){ return log10(num)+1; } //numの桁数を求める
uint64_t combinations2(uint64_t n, uint64_t k) {
    uint64_t r = 1;
    for (uint64_t d = 1; d <= k; ++d) {
        r *= n--;
        r /= d;
    }
    return r;
}
int main()
{
    ll N,M;
    cin >> N >> M;
    cout << combinations2(N,2) + combinations2(M,2) << endl;
}

Measured memory_bytes: 256
n = int(input())
a = []
for x in input().split():
    a.append(int(x))

cnt_minus = sum(x<0 for x in a)
cnt_zero = sum(x==0 for x in a)

if cnt_minus % 2 == 0 or cnt_zero > 0:
    print(sum(abs(x) for x in a))
else:
    y = min(abs(x) for x in a)
    while y == 0:
        a.remove(0)
        y = min(abs(x) for x in a)
    print(sum(abs(x) for x in a) - 2 * y)


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

typedef pair<int,int> P;

int main(void){
	int n;

	while(1){
		vector<P> p;
		for(int i=0;i<2;i++){
			cin>>n;
			if(n == 0) return 0;

			for(int j=0;j<n;j++){
				int x,y;
				cin>>x>>y;
				p.push_back(P(x,y));
			}
		}

		n = p.size();
		sort(p.begin(),p.end());

		int res = 0;
		int dp[n];
		memset(dp,0,sizeof(dp));
		for(int i=0;i<n;i++){
			for(int j=0;j<i;j++){
				if(p[j].first < p[i].first &&
					 p[j].second < p[i].second &&
					 dp[i] < dp[j] + 1){
					dp[i] = dp[j] + 1;
				}
			}
			res = max(res,dp[i]);
		}

		cout<<res+1<<endl;
	}

	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <algorithm>

using namespace std;
long long X[100005];
int main() {
    long long N, A, B;
    cin>>N>>A>>B;
    for (int i = 0; i < N; ++i)
        cin>>X[i];
    long long res = 0;
    for (int i = 0; i < N-1; ++i)
        res += min(B, A*(X[i+1]-X[i]));
    cout<<res<<endl;
    return 0;
}

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

#define rep(i, x, n) for (int i = x; i < n; i++)
typedef long long ll;

const int INF = 1e9 + 7;

using namespace std;

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

  int n, m;
  cin >> n >> m;

  vector<pair<int, string>> result(m);
  rep (i, 0, m) {
    int p;
    string s;
    cin >> p >> s;
    p--;
    result[i] = make_pair(p, s);
  }

  vector<int> memo(n, 0);
  vector<int> pe(n, 0);
  vector<int> ac(n, 0);
  rep (i, 0, m) {
    if (result[i].second == "AC" && memo[result[i].first] != 1) {
      ac[result[i].first] = 1;
      memo[result[i].first] = 1;
    } else if (result[i].second == "WA" && memo[result[i].first] != 1) {
      pe[result[i].first]++;
    }
  }

  int res_ac = 0;
  int res_pe = 0;
  rep (i, 0, n) {
    if (ac[i]) {
      res_ac++;
      res_pe += pe[i];
    }
  }

  cout << res_ac << " " << res_pe << endl;

	return 0;
}

Measured memory_bytes: 7680
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(a,b) for(int a=0;a<(b);++a)
#define REP1(i,n) for(int i=1;i<=(n);++i)
#define debug(x) cerr<<#x<<": "<<x<<'\n'
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
#define INF (1<<29)
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

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

template<class T=int>
T in(){T x;cin>>x;return (x);}
template<class T>
void print(T& x){cout<<x<<'\n';}

const int MOD =(int)1e9+7;
const int MAX =510000;
ll fac[MAX],finv[MAX],inv[MAX];
void COMint(){
    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;
}
ll gcd(ll a,ll b){
    if(b==0)return a;
    if(a>b){
        swap(a,b);
    }
    return gcd(a,b%a);
}
ll lcm(ll a,ll b){
    ll g;g=gcd(a,b);
    return a*b/g;
}
bool compare_by_b(pair<int, int> a, pair<int, int> b) {
    if(a.second != b.second){
        return a.second < b.second;
    }else{
        return a.first < b.first;
    }
}

bool compare_by_a(pair<int, int> a, pair<int, int> b) {
    if(a.first != b.first){
        return a.first < b.first;
    }else{
        return a.second < b.second;
    }
}
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N=in();
    vector<ll> A(N);
    REP(i,N){
        cin>>A[i];
    }
    sort(all(A));
    REP(i,N-1){
        if(A[i]==A[i+1]){
            cout<<"NO"<<endl;
            return 0;
        }
    }
            cout<<"YES"<<endl;
    return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <numeric>
#include <bitset>

using namespace std;

typedef long long ll;

long long GCD(long long a, long long b){if(b==0)return a;return GCD(b,a%b);}

int N, M; 
vector<vector<int>> S(20);
vector<int> P;
vector<int> K;
int res = 0;

int main() {
    cin >> N >> M;
    for (int i = 0; i < M; ++i) {
        int k; cin >> k;
        K.push_back(k);
        for (int j = 0; j < k; ++j) {
            int s; cin >> s;
            S[i].push_back(s);
        }
    }

    for (int i = 0; i < M; ++i) {
        int p; cin >> p;
        P.push_back(p);
    }

    for (int i = 0; i < pow(2, N); ++i) {
        bool ok = true;
        for (int j = 0; j < M; ++j) {
            int temp_i = 0;
            for (int k = 0; k < K[j]; ++k) {
                temp_i |= (1<<S[j][k]-1);
            }
            ok &= __builtin_popcount(i & temp_i) % 2 == P[j];
        }
        if (ok) ++res;
    }
    cout << res << endl;
}


Measured memory_bytes: 256