akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;

int A[110][110];
int col[110];
int row[110];
int r,c;
int main(){
	while(cin >> r >> c){
		int sum = 0;
		for(int i=1;i<=r;i++){
			for(int j=1;j<=c;j++){
				cin >> A[i][j];
				row[i] += A[i][j];
				col[j] += A[i][j];
				sum += A[i][j];
			}
		}
		for(int i=1;i<=r+1;i++){
			for(int j=1;j<=c+1;j++){
				if(i!=r+1){
					if(j!=c+1) cout << A[i][j] << " ";
					else cout << row[i] << endl;
				}else if(j!=c+1) cout << col[j] << " ";
				else cout << sum << endl;
			}
		}
	}
}


Measured memory_bytes: 3108
import java.util.*;
 
public class Main{
    public static void main(String args[] ) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] array = new int[n];
        int on = 0;
        for (int i = 0; i < n; i++) {
            array[i] = sc.nextInt();
        }
        int m = 0;
        int count = 0;
        for (int i = 0; i < n; i++) {
            m = array[m] - 1;
            count++;
            if (m == 1) {
                break;
            }
        }
        if (count == n) {
            System.out.println(-1);
        } else {
            System.out.println(count);
        }
    }
}


Measured memory_bytes: 51240
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<utility>
using namespace std;
typedef long long ll;
#define rep(i,a,n)	for(int i=a;i<n;i++)
#define rrep(i,a,n) for(int i=(a-1);i>=n;i--)
 
ll gcd(ll a,ll b){
	if(b==0)return a;
	return gcd(b,a%b);
}
ll lcm(ll a,ll b){
	ll g=gcd(a,b);
	return a/g*b;
}
 
ll digitsum(ll a){
	ll x=0;
	while(a>0){
		x+=a%10;
		a/=10;
	}
	return x;
}
int main(){
	ll x,a,b;
	cin>>x>>a>>b;
	if((b-a)<=0)cout<<"delicious"<<endl;
	else if((b-a)<=x)cout<<"safe"<<endl;
	else cout<<"dangerous"<<endl;
}

Measured memory_bytes: 256
using namespace std;
#include <bits/stdc++.h>
#define frr(i, r, l) for(int i = r; i >= l; --i)
#define fr(i, l, r) for(int i = l; i < r; ++i)
#define forit(it, type, var) for(type::iterator it = var.begin(); it != var.end(); it++)
#define ii pair<int, int>
#define iii pair<int, ii>
#define MEMS(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define m_p make_pair
#define pb push_back
#define ll long long
#define ld long double
typedef pair<ll, ll> iPair; 
priority_queue< ll, vector <ll> , greater<ll>>pq1,pq2;
#define maxN 1000000000000000000
ll power(ll a,ll b){ll res=1;while(b>0){res*=a;b--;}return res;}
int main()
{
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,m,st[200005]={0},x,y,mod=998244353,pref[200005]={0};
    set<ll>s;
    vector<pair<ll,ll>>v;
    cin>>n>>m;
    fr(i,0,m)
    {
        cin>>x>>y;
        v.pb({x,y});
    }
    sort(v.begin(),v.end());
    
    ll st2;
    st[1]=1;
    ll sum=0;
    fr(i,1,n+1)
    {
        fr(j,0,v.size())
        {
            ll fir=v[j].first;
            ll sec=v[j].second;
            if(i-fir>=1)
            {
                if(i-sec-1>=1)
                st2=pref[i-sec-1];
                else
                st2=0;

                st[i]=(st[i]+pref[i-fir]-st2)%mod;
            }
        }
       // cout<<st[i]<<" ";
        sum+=st[i];
        pref[i]=sum;
    }
    cout<<endl;
    cout<<st[n]<<endl;
    return 0;
}

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

using namespace std;
using LL = long long;

const int MOD = 998244353;

class Edge{
public:
    LL from,to, value;
    Edge(int f,int t, int c){
        from = f;
        to = t;
        value = c;
    }
};

int main(){
    int N;cin >> N;
    vector<vector<int>> E(N);
    for(int i = 0;i < N - 1;i++){
        int a,b;cin >> a>> b;
        a--,b--;
        E[a].push_back(b);
        E[b].push_back(a);
    }
    vector<int> flag(N, -1);
    flag.front() = 0;
    flag.back() = 1;
    queue<int> que;
    que.push(0);
    que.push(N-1);
    while(!que.empty()){
        int q = que.front();
        que.pop();
        for(auto a : E[q]){
            if(flag[a] == -1){
                flag[a] = flag[q];
                que.push(a);
            }
        }
    }
    int F = 0,S = 0;
    for(auto a : flag){
        if(a == 0)F++;
        else S++;
        //cout<<a<<endl;
    }

    if(S < F){
        cout<<"Fennec"<<endl;
    }else{
        cout<<"Snuke"<<endl;
    }
}


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

using namespace std;

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

    int a,b;
    scanf("%d%d",&a,&b);
    if(a<b)
    {
        for(int i=0;i<b;i++)
        printf("%d",a);
    }
    else
    {
        for(int i=0;i<a;i++)
        printf("%d",b);
    }
    printf("\n");
    return 0;
}


Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author aajisaka
 */

#include<bits/stdc++.h>

using namespace std;

void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define SPEED ios_base::sync_with_stdio(false);cin.tie(nullptr)
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
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; }

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;

constexpr long double PI = 3.14159265358979323846264338327950288L;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

class DFloorFunction {
public:
    void solve(istream& cin, ostream& cout) {
      SPEED;
      ll a, b, n; cin >> a >> b >> n;

      ll x = max(1LL, min(b-1, n));

      ll ret = a*x/b - a*(x/b);
      cout << ret << endl;

    }
};

signed main() {
  DFloorFunction solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define rep2(i, s, n) for(int i=s; i<(n); ++i)
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;

template<typename T>
using priority_queue_rev = priority_queue<T, vector<T>, greater<T> >;

static const int INTINF = (2147483647 >> 1); // 10^9 + 5000
static const ll LLINF = (9223372036854775807 >> 1);
static const int MAX = 1e5+1;
static const ll MOD = 1e9+7;

namespace Kunitaka{
    template<
        typename TYPE,
        std::size_t SIZE
    >
    std::size_t array_length(const TYPE (&array)[SIZE])
    {
        return SIZE;
    }

    template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
    template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
}
using namespace Kunitaka;
namespace Printer{
    void br(){
        cout << endl;
    }

    void loop_cnt(int i){
        cout << "i = " << i << endl;
    }

    void loop_cnt(int i, int j){
        cout << "i = " << i << ", " << "j = " << j << endl;
    }

    template<class T>
    void print(T x){
        cout << x << endl;
    }

    template<class T, class S>
    void print(T x, S y){
        cout << x << "," << y << endl;
    }

    template<class T, class S, class U>
    void print(T x, S y, U z){
        cout << x << "," << y << "," << z << endl;
    }

    template<class T, class S>
    void print(pair<T, S> p){
        cout << p.first << ", " << p.second << endl;
    }

    template<
        typename TYPE,
        std::size_t SIZE
    >
    void print(const TYPE (&array)[SIZE]){
        int lim = array_length(array);
        for(int i=0; i<lim; i++){
            if(i) cout << " ";
            cout << array[i];
        }
        cout << endl;
    }

    template<class S>
    void print(vector<S> v){
        for(int i=0; i<v.size(); i++){
            if(i) cout << " ";
            cout<< v[i];
        }
        cout << endl;
    }

    template<class S>
    void print(vector<vector<S> > vv){
        for(int i=0; i<vv.size(); i++){
            for(int j=0; j<vv[i].size(); j++){
                if(j) cout << " ";
                cout << vv[i][j];
            }
            cout << endl;
        }
    }

    void yesno(bool x){
        if(x) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
};
using namespace Printer;

int main(int argc, const char * argv[]) {
    //提出時、消す----//
    //--------------//


    // input
    cout << fixed << setprecision(10);
    int a, b, c; cin >> a >> b >> c;
    int tmp = b;
    b = a;
    a = tmp;
    tmp =a;
    a = c;
    c = tmp;

    cout << a <<" " << b << " " << c << endl;
    
    
    return 0;
}


Measured memory_bytes: 256
import math
N = int(input())

sqrt_N = int(math.sqrt(N))
count = 0
tmp = [[0] * 2 for i in range(N+1)]
for i in range(1,sqrt_N+1):
    for j in range(1,sqrt_N+1):
        for k in range(1,sqrt_N+1):
            ff = i**2 + j**2 + k**2 + i*j + j*k + k*i
            if ff <= N:
                tmp[ff][1] += 1

for i in range(1,N+1):
    print(tmp[i][1])





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

using namespace std;
typedef long long ll;

inline int at(ll x, int k){ return (x >> k) & 1; }
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,a,b) for(ll i=a;i>=b;i--)


int main() {
	ll a,b,c,k;
	cin >> a >> b >> c>> k;
	if(k<=a){
		cout << k << endl;
	}
	else if(k>a && k<=a+b){
		cout << a << endl;
	}
	else{
		cout << a-(k-a-b) << endl;
	}

}


Measured memory_bytes: 3624
//#define _GLIBCXX_DEBUG

#include<bits/stdc++.h>
#define PI 3.14159265359
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
const int INF= 1e9+5;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll> >vvl;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> T;
const ll MOD=1000000007LL;
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
struct UnionFind {
    vector<ll> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(ll N) : par(N) { //最初は全てが根であるとして初期化
        for(ll i = 0; i < N; i++) par[i] = i;
    }

    ll root(ll x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(ll x, ll y) { // xとyの木を併合
        ll rx = root(x); //xの根をrx
        ll ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(ll x, ll y) { // 2つのデータx, yが属する木が同じならtrueを返す
        ll rx = root(x);
        ll ry = root(y);
        return rx == ry;
    }
};
int main(){
  ll n,m;cin>>n>>m;
  vl p(n);
  rep(i,n)cin>>p[i];
  vl x(m),y(m);
  rep(i,m)cin>>x[i]>>y[i];
  UnionFind Tree(n);
  rep(i,m)Tree.unite(p[x[i]-1]-1,p[y[i]-1]-1);
  ll count=0;
  rep(i,n){
    if(Tree.same(i,p[i]-1))count++;
  }
  cout<<count<<endl;
}

Measured memory_bytes: 3328
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<deque>
#include<bitset>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
typedef pair<int,int> P;
template<class T> inline bool chmax(T&a , T b){ if(a<b){ a=b; return true; } else{ return false; } }
template<class T> inline bool chmin(T&a , T b){ if(a>b){ a=b; return true; } else{ return false; } } 

const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

int main(){
    ll a,b,n;
    cin >> a >> b >> n;
    ll ans=0;
    if(n>=b-1){
        ans = a*(b-1)/b - a*((b-1)/b);
        cout << ans << endl;
    }else{
        ans = a*n/b - a*(n/b);
        cout << ans << endl;
    }
}

Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <cmath>

using namespace std;
using ll = long long;

int gcd(int a, int b) { return (b == 0) ? a : gcd(b, a % b); }

#define CIN(T, x) T x; cin >> x;
#define CINS(T, x, N) vector<T> x(N); for(int i = 0; i < (N); i++) { cin >> x[i]; }
#define SHOW(x) for(int i = 0; i < x.size(); i++) { cout << x[i] << " "; } cout << "\n";
#define SHOW2(x) for(int j = 0; j < x.size(); j++) { SHOW(x[j]); } cout << "\n";


int main() {

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

    CIN(int, H);
    CIN(int, W);
    CINS(string, A, H);

    vector<vector<int>> board(H, vector<int>(W, INF));
    queue<pair<int, int>> q;

    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if ( A[i][j] == '#' ) {
                board[i][j] = 0;
                q.push(make_pair(i, j));
            }
        }
    }

    while ( !q.empty() ) {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if ( nx >=0 && nx < W && ny >=0 && ny < H ) {
                if ( board[ny][nx] == INF ) {
                    q.push(make_pair(ny, nx));
                }
                board[ny][nx] = min(board[ny][nx], board[y][x] + 1);
            }
        }
    }

    // SHOW2(board);

    int MAX = 0;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            MAX = max(MAX, board[i][j]);
        }
    }

    cout << MAX << "\n";
    return 0;
}

Measured memory_bytes: 13456
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define LONGMAX 1e18
#define dd double
#define MOD 998244353 
# define my_sizeof(type) ((char *)(&type+1)-(char*)(&type)) 
#define nl cout<<endl
#define rt ll Q[100005]={0}
#define mp make_pair
#define endl "\n"
#define test() ll t;cin>>t;while(t--)
#define pb push_back
#define ff first	
#define ss second
#define all(v) v.begin(),v.end()
#define s(ar,n) sort(ar,ar+n)
#define rs(ar,n) sort(ar, ar+n, greater<ll>()) 
#define oa(a,n) for(ll i=0;i<n;i++)cout<<a[i]<<" ";nl
#define cn(a,n) for(ll i=0;i<n;i++)cin>>a[i];
#define ov(a,n) for(ll i=n-1;i>=0;i--)cout<<a[i]<<" ";nl
#define maxa(ar,N) *max_element(ar,ar+N)
#define mina(ar,N) *min_element(ar,ar+N)
#define INF 1e9
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
ll power(ll x, ll y){ll res=1;x=x%MOD;while(y>0){if(y&1)res = (res*x) % MOD;y = y>>1;x = (x*x) % MOD;}return res;}  
ll logtwo(ll n){if(n==1)return 0;return logtwo(n/2)+1;}
void ceilsearch(ll ar[],ll low,ll high,ll x,ll &y){if(low>high)return;ll mid=(low+high)/2;if(ar[mid]>=x){y=mid;ceilsearch(ar,low,mid-1,x,y);}else{ceilsearch(ar,mid+1,high,x,y);}}
signed main()
{
	fastio();	
  	ll ar[]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  	ll N;
  	cin>>N;
  	cout<<ar[N-1];
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define PI 3.14159265358979323846
#define MAXINF (1e18L)
#define INF (1e9L)
#define EPS (1e-9)
#define MOD ((ll)(1e9+7))
#define REP(i, n) for(int i=0;i<int(n);++i)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define ALL(v) v.begin(),v.end()
#define FIND(v,x) (binary_search(ALL(v),(x)))
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v));reverse(ALL(v))
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define pb push_back
#define fi first
#define se second
using namespace std;
template<class A>void pr(A a){cout << (a) << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;pr(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;pr(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;pr(b,c,d);}
template<class T> inline bool chmin(T& a, T b){return a>b ? a=b, true : false;}
template<class T> inline bool chmax(T& a, T b){return a<b ? a=b, true : false;}
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;

int v[] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};

int main(void)
{
    int K;
    cin >> K;
    pr(v[K-1]);
}

Measured memory_bytes: 256
d, g = map(int, input().split())
pc = [list(map(int, input().split())) for _ in range(d)]
m = 10000
for i in range(2**d):
    cur = bin(i)[2:].zfill(d)
    s = 0
    c = 0
    nu = []
    for i in range(d):
        if cur[i] == '0':
            nu.append(i)
        else:
            s += (i+1) * 100 * pc[i][0] + pc[i][1]
            c += pc[i][0]
    if g > s:
        if g - s <= (nu[-1]+1) * 100 * pc[nu[-1]][0]:
            c += (g-s-1)//((nu[-1]+1)*100)+1
            m = min(c, m)
    else:
        m = min(c, m)
print(m)

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

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
using namespace std;

int main() {
    int x, y;
    cin >> x >> y;
    bool flag = false;
    rep(i, x + 1) {
        int t = i;
        int k = x - i;
        if (t * 2 + k * 4 == y) {
            flag = true;
        }
    }

    cout << (flag ? "Yes" : "No") << endl;


    return 0;
}

Measured memory_bytes: 3632
from collections import deque


def bfs(x, w):
    q = deque()
    q.append((x, w))

    while len(q):
        x, w = q.popleft()
        leaves[x] += w
        w = leaves[x]
        for nx in edge[x]:
            if V[nx] == 0:
                V[nx] = 1
                q.append((nx, w))


N, Q = map(int, input().split())
edge = [[] for _ in range(N)]
leaves = [0] * N
V = [0] * N

for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edge[a].append(b)
    edge[b].append(a)

for q in range(Q):
    p, x = map(int, input().split())
    p -= 1
    leaves[p] += x

V[0] = 1
bfs(0, 0)
for i in range(N - 1):
    print(leaves[i], end=' ')
print(leaves[N - 1])


Measured memory_bytes: 106828
X, K, D = map(int, input().split())
X = abs(X)
Kmax = X // D
if Kmax >= K:
  print(X - K * D)
else:
  Kmod = K - Kmax
  if Kmod % 2  == 0:
    print(X - Kmax * D)
  else:
    print(abs(X - (Kmax+1) * D))

Measured memory_bytes: 9212
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char) 
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n: i128 = read();
    let mut money: i128 = 0;
    while n > money {
        money += 1000;
    }

    println!("{}", money-n);
}

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

int main(){
  int n;
  cin >> n;
  vector<int> hoge(n);
  for (int i = 0; i < n; i++){
    cin >> hoge.at(i);
  }
  
  int count = 0;
  for (int i = 1; i < n - 1; i++){
    if ((hoge[i - 1] < hoge[i] && hoge[i] < hoge[i + 1]) || (hoge[i - 1] > hoge[i] && hoge[i] > hoge[i + 1])){
      count += 1;
    }
  }
  
  cout << count << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for ( int i = 0; i < (n); ++i )
using namespace std;
using ll = long long int;
const long long int INF = 1001001001001001LL;
const int inf = 1000000007;
long long int MOD = 1000000007LL;
double PI = 3.1415926535897932;


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

    int N;
    ll W;
    cin >> N >> W;
    vector<ll> w(N);
    vector<ll> v(N);
    rep(i, N) cin >> w[i] >> v[i];
    
    ll V = *max_element( v.begin(), v.end() );
    vector<vector<ll>> dp(N+1, vector<ll>(N*V+1, INF));
    dp[0][0] = 0;
    rep(i, N) {
        rep(j, N*V+1) {
            ll nj = j - v[i];
            if( nj >= 0 ) dp[i+1][j] = min( dp[i][j], dp[i][nj] + w[i] );
            else dp[i+1][j] = dp[i][j];
        }
    }
    
    ll ans = 0LL;
    rep(j, N*V+1) if( dp[N][j] <= W ) ans = j;
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 80256
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
#s=input().rstrip()

k,s=MI()
count=0
for i in range(0,k+1):
    for j in range(0,k+1):
        if 0<=s-i-j<=k:
            count+=1
print(count)

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

int main() {
	// your code goes here
ll n,i,j;
cin>>n;
ll ar[n+1];
for(i=1;i<=n;i++)
 {
   cin>>ar[i]; 
 }
for(i=n;i>=1;i-=2)
 {
   cout<<ar[i]<<" "; 
 }
if(n%2==0)
{
for(i=1;i<=n;i+=2)
 {
   cout<<ar[i]<<" "; 
 }
}
else
 {
  for(i=2;i<=n;i+=2)
  {
   cout<<ar[i]<<" "; 
  }  
 }
	return 0;
}

Measured memory_bytes: 3712
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pi 3.1415926536
#define pb push_back
#define N 1000000007
#define M 998244353
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define nrep(i,a,b) for(int i=a;i>=b;i--)
#define pl pair<ll,ll>
#define pi pair<int,int>
#define pll pair< ll, pair<ll,ll> > 
#define pii pair< int, pair<int,int> >
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    double l,t,T,x,y,z;
    cin>>x>>y>>z;
    if(x/z <= y) cout<<"Yes\n";
    else cout<<"No\n";
}

Measured memory_bytes: 3732
#include <iostream>
#include <cstdio>
#include <cctype>
using namespace std;
 
int main() 
{
    char ch;
    int cnt[26] = {};
     
    while(cin >> ch){
        ch = tolower(ch);
        if( isalpha(ch)){
            cnt[ch - 'a']++;
        }
    }
    for( int i = 0;i < 26;i++){
        printf("%c : %d\n",i+'a',cnt[i]);
    }
    return 0;
}

Measured memory_bytes: 3208
#include <stdio.h>

int main(void){
    int how_many;
    scanf("%d", &how_many);

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

    int total = 0;
    for (int i = 0; i < how_many; i++) {
        for (int j = i+1; j < how_many; j++) {
            total += takos[i] * takos[j];
        }
    }

    printf("%d\n", total);

    return 0;
}


Measured memory_bytes: 128
//
// Created by Myabu on 2020/01/26.
//

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <utility>
#include <math.h>
#include <stack>
#include <queue>
#include <cstdio>
#include <numeric>
#include <iomanip>

using namespace std;


int main(void){
    int N,A;
    cin>>N>>A;
    
    cout<<N*N-A<<endl;
    
    
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;

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

    vector<int> c(5);
    rep(i, n) {
        string s;
        cin >> s;

        if(s[0] == 'M') {
            c[0]++;
        }
        else if(s[0] == 'A') {
            c[1]++;
        }
        else if(s[0] == 'R') {
            c[2]++;
        }
        else if(s[0] == 'C') {
            c[3]++;
        }
        else if(s[0] == 'H') {
            c[4]++;
        }
    }

    ll ans = 0;
    rep(i, 3) {
        for(int j = i+1; j < 4; j++) {
            for(int k = j+1; k < 5; k++) {
                ans += (ll)c[i]*c[j]*c[k];
            }
        }
    }

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

Measured memory_bytes: 256
S=input()
ans=0
cnt=0
for s in S:
    if s in "A":
        cnt+=1
    elif s in "C":
        cnt+=1
    elif s in "G":
        cnt+=1
    elif s in "T":
        cnt+=1   
    else:
        cnt=0
    ans=max(ans,cnt)
print(ans)

Measured memory_bytes: 3060
i = 0
x = []
y = []
while(1):
    a,b = map(int,input().split())
    if a <= b:
        x.append(a)
        y.append(b)
    else :
        x.append(b)
        y.append(a)
    if x[i] == 0 and y[i] == 0:
        break
    i += 1

for j in range(i):
    print(x[j],y[j])



Measured memory_bytes: 6132
n = int(input())
s = input()
r = []
g = []
b = []
for i in range(n):
    if s[i] == "R":
        r.append(i)
    elif s[i] == "G":
        g.append(i)
    else:
        b.append(i)
ans = len(r)*len(g)*len(b)
for i in b:
    for j in g:
        a = max(i,j)
        u = min(i,j)
        if a*2-u >= 0 and a*2-u < n :
            if s[a*2-u] == 'R':
                ans -= 1
        if 2*u-a >= 0 and 2*u-a < n:
            if s[2*u-a] == 'R':
                ans -= 1
        if (a-u)%2 == 0 and u+(a-u)/2 >= 0 and u+(a-u)/2 < n:
            if s[u+(a-u)//2] == 'R':
                ans -= 1
print(ans)


Measured memory_bytes: 9244
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

# 最小公倍数
def gcd(a, b):
	if a < b:
		a, b = b, a
	while a % b != 0:
		a, b = b, a % b
	return b
 
# 最大公約数 
def lcm(a, b):
	y = a*b / gcd(a, b)
	return int(y)

def primes_for(n):
  is_prime = [True] * (n + 1)
  is_prime[0] = False
  is_prime[1] = False
  for i in range(2, n + 1):
      for j in range(i * 2, n + 1, i):
          is_prime[j] = False
  return [i for i in range(n + 1) if is_prime[i]]

# O(√A)
def isPrime(n):
  if n < 2:
    # 2未満は素数でない
    return False
  if n == 2:
    # 2は素数
    return True
  for p in range(2, n):
      if n % p == 0:
        # nまでの数で割り切れたら素数ではない
        return False
  # nまでの数で割り切れなかったら素数
  return True

x = INT()

while isPrime(x) == False:
  x = x + 1
print(x)

Measured memory_bytes: 5200
#!/usr/bin/env python3
# GRL_5_A: Tree - Diameter of a Tree


class Edge:
    __slots__ = ('v', 'w')

    def __init__(self, v, w):
        self.v = v
        self.w = w

    def either(self):
        return self.v

    def other(self, v):
        if v == self.v:
            return self.w
        else:
            return self.v


class WeightedEdge(Edge):
    __slots__ = ('v', 'w', 'weight')

    def __init__(self, v, w, weight):
        super().__init__(v, w)
        self.weight = weight


class Graph:
    def __init__(self, v):
        self.v = v
        self._edges = [[] for _ in range(v)]

    def add(self, e):
        self._edges[e.v].append(e)
        self._edges[e.w].append(e)

    def adj(self, v):
        return self._edges[v]

    def edges(self):
        for es in self._edges:
            for e in es:
                yield e


def diameter(graph):
    def dfs(s):
        visited = [False] * graph.v
        weights = [0] * graph.v
        stack = [(s, 0)]
        while stack:
            v, weight = stack.pop()
            if not visited[v]:
                visited[v] = True
                weights[v] = weight
                for e in graph.adj(v):
                    w = e.other(v)
                    if not visited[w]:
                        stack.append((w, weight + e.weight))
        return weights

    v0 = 0
    ws0 = dfs(v0)
    v1 = max((wg, v) for v, wg in enumerate(ws0))[1]
    ws1 = dfs(v1)
    v2 = max((wg, v) for v, wg in enumerate(ws1))[1]

    return max(ws0[v2], ws1[v2])


def run():
    n = int(input())
    g = Graph(n)

    for _ in range(n-1):
        s, t, w = [int(i) for i in input().split()]
        g.add(WeightedEdge(s, t, w))

    print(diameter(g))


if __name__ == '__main__':
    run()



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

using namespace std;

int main(){
	while(1){
		int n; cin >> n;
		if(!n) break;
		vector<vector<int> > lists(n);
		for(int i=0; i<n; i++){
			int m; cin >> m;
			lists[i].resize(m);
			for(int j=0; j<m; j++) cin >> lists[i][j];
			sort(lists[i].begin(), lists[i].end());
		}
		int k; cin >> k;
		vector<int> l(k);
		for(int i=0; i<k; i++) cin >> l[i];
		sort(l.begin(), l.end());

		int ans = -1;
		int candCount = 0;
		for(int i=0; i<n; i++){
			int idx = 0;
			for(int j=0; j<lists[i].size(); j++){
				if(idx == k) break;
				if(lists[i][j] == l[idx]) idx++;
			}
			if(idx == k){
				candCount++;
				ans = i+1;
			}
		}
		if(candCount==1){
			cout << ans << endl;
		} else{
			cout << -1 << endl;
		}
	}
	return 0;
}


Measured memory_bytes: 3200
#![allow(non_snake_case, unused)]
use std::cmp::*;
use std::collections::*;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        mut x: i64,
        mut k: i64,
        d: i64,
    }
    x = x.abs();
    let mut cnt = x / d;
    if cnt > k {
        cnt = k;
        x -= d * cnt;
        println!("{}", x);
        return;
    }
    x -= d * cnt;
    k -= cnt;
    if k % 2 != 0 {
        x = (x - d).abs();
    }
    println!("{}", x);
}


Measured memory_bytes: 2120
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int bar[] = new int[n];
        for (int i = 0; i < n; ++i){
            bar[i] = sc.nextInt();
        }
        
        for (int i = 0; i < n-1; ++i){
            if (bar[i] > bar[i+1]){
                bar[i+1] += 1;
                if (bar[i] > bar[i+1]){
                System.out.println("No");
                System.exit(0);
                }
            }
        }
        
        System.out.println("Yes");
    }
}

Measured memory_bytes: 50124
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define INF 1<<30
#define LINF 1LL<<60

/*
<url:https://beta.atcoder.jp/contests/arc087/tasks/arc087_a>
問題文============================================================
 長さN(1<=N<=10^5)の正整数の数列a( 1<= ai <= 10^9)が与えられる
 
 このとき、数列を a の各要素xについてaに値xがちょうどx個含まれる
 という条件を満たすために取り除くべき要素の最小個数を求めよ
=================================================================

解説=============================================================

================================================================
*/
int main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
    int N; cin >> N;
    map<int,int> m;
    for(int i = 0; i < N;i++){
        int a; cin >> a;
        m[a]++;
    }
    ll res = 0;
    for(auto v:m){
        res += (v.first <= v.second)? v.second - v.first : v.second;
    }
    cout << res << endl;
	return 0;
}


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

int gcd(int a, int b){
    if(a < b) swap(a, b);
    int r = a % b;
    return r > 0 ? gcd(b, r) : b;
}

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

    int x, y;
    cin >> x >> y;
    cout << x + y - gcd(x, y) + 1 << endl;

    return 0;
}


Measured memory_bytes: 3188
<?php
    $taro_point = 0;
    $hanako_point = 0;

    $qty = trim(fgets(STDIN));
    
    for($i = 0; $i < $qty; $i++){
        list($taro_card, $hanako_card) = explode(" ",trim(fgets(STDIN)));

        if($taro_card > $hanako_card) {
            $taro_point += 3;
        } elseif ($taro_card < $hanako_card) {
            $hanako_point += 3;
        } else {
            $taro_point++;
            $hanako_point++;
        }
    }

    echo "$taro_point $hanako_point\n";
    

Measured memory_bytes: 15328
#include <iostream>
#include <set>
#include <algorithm>
#include <string>
int main()
{
	int X, N;
	std::cin >> X >> N;
	std::set<int> p;
	for (int i = 0; i < N; ++i) {
		int n;
		std::cin >> n;
		p.insert(n);
	}
	if (N == 0) {
		std::string s;
		std::cin.ignore();
		std::getline(std::cin, s);
	}
	for (int i = 0; ; ++i) {
		if (p.find(X - i) == p.end()) {
			std::cout << X - i << std::endl;
			break;
		}
		if (p.find(X + i) == p.end()) {
			std::cout << X + i << std::endl;
			break;
		}
	}
	return 0;
}

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

int main(){
  int A,B,C;
  long long K;
  cin >> A >> B >> C >> K;
  if(abs(A-B)>1000000000000000000){
    cout << "Unfair" << endl;
  }
  else if(K%2==0){
    cout << A-B << endl;
  }
  else{
    cout << B-A << endl;
  }
}

Measured memory_bytes: 3636
#define _USE_MAT_DEFINES
#include<iostream>
#include <iomanip>
#include<stdio.h>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include <queue>
#include <utility>
#include <map>
#include <set>
#include <stack>
#include <deque>
#include <numeric>
#include <functional>
using namespace std;

#define MOD 1000000007;//1e9+7

void solve() {
    int K, X;
    cin >> K >> X;

    if (500 * K >= X)cout << "Yes";
    else cout << "No";

    return;
}

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
#define int long long
using namespace std;
typedef pair<int,int>P;
typedef pair<int,P>P2;
#define F first
#define S second
int dy[]={0,0,1,-1,1,-1,1,-1};
int dx[]={1,-1,0,0,1,-1,-1,1};

signed main(){
  int L,R,ans=222222;
  cin>>L>>R;

  if(2500<R-L){
    cout<<0<<endl;
    return 0;
  }
  for(int i=L;i<=R;i++){
    for(int j=i+1;j<=R;j++){
      ans=min(ans,(i*j)%2019);
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskA solver = new TaskA();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskA {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            char[] s = in.next().toCharArray();
            char[] model = {'Y', 'A', 'K', 'I'};
            if (s.length < 4) {
                out.println("No");
                return;
            }
            for (int i = 0; i < model.length; i++) {
                if (s[i] != model[i]) {
                    out.println("No");
                    return;
                }
            }
            out.println("Yes");
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

    }
}



Measured memory_bytes: 21460
import bisect,collections,copy,heapq,itertools,math,string
import sys
def S(): return sys.stdin.readline().rstrip()
def M(): return map(int,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
N = I()
ans = 0
for i in range(1, N+1):
    ans += i
print(ans)

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

		String n = sc.next();

		if (n.charAt(0)==n.charAt(1)&&n.charAt(1)<n.charAt(2)) {
			int data = Character.getNumericValue(n.charAt(0))+1;
			System.out.print(data);
			System.out.print(data);
			System.out.print(data);
			System.out.println();
			System.exit(0);
		}

		if (n.charAt(0)==n.charAt(1)&&n.charAt(0)==n.charAt(2)) {
			System.out.println(n);
		}else{
			if (n.charAt(0)>=n.charAt(1)) {
				System.out.print(n.charAt(0));
				System.out.print(n.charAt(0));
				System.out.print(n.charAt(0));
				System.out.println();
			}else{
				int data = Character.getNumericValue(n.charAt(0))+1;
				System.out.print(data);
				System.out.print(data);
				System.out.print(data);
				System.out.println();
			}
		}

	}
}


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

class P
{
    static void Main()
    {
        int[] s = Console.ReadLine().Split().Select(int.Parse).ToArray();
        Console.WriteLine((s[0] % 3) * (s[1] % 3) * ((s[0] + s[1]) % 3) == 0 ? "Possible" : "Impossible");
    }
}

Measured memory_bytes: 13396
N = int(input())
s = input()
S = ['SSS', 'SSW', 'SWW', 'WWW', 'WWS', 'WSS', 'SWS', 'WSW']
ans = []
for n in range(4):
    ans = []
    if len(s) == 3:
        print(-1)
        exit()
    elif s[1] == 'o' and n == 0:
        ans.append('S')
        ans.append('S')
    elif s[1] == 'x' and n == 0:
        ans.append('W')
        ans.append('S')
    elif s[1] == 'o' and n == 1:
        ans.append('S')
        ans.append('W')
    elif s[1] == 'x' and n == 1:
        ans.append('S')
        ans.append('W')
    elif s[1] == 'o' and n == 2:
        ans.append('W')
        ans.append('S')
    elif s[1] == 'x' and n == 2:
        ans.append('W')
        ans.append('W')
    elif s[1] == 'o' and n == 3:
        ans.append('W')
        ans.append('W')
    elif s[1] == 'x' and n == 3:
        ans.append('S')
        ans.append('S')

    for i in range(1, N):
        if ans[i - 1] == 'S':
            if ans[i] == 'S':
                if s[i] == 'o':
                    ans.append('S')
                else:
                    ans.append('W')
            else:
                if s[i] == 'o':
                    ans.append('W')
                else:
                    ans.append('S')
        else:
            if ans[i] == 'S':
                if s[i] == 'o':
                    ans.append('W')
                else:
                    ans.append('S')
            else:
                if s[i] == 'o':
                    ans.append('S')
                else:
                    ans.append('W')
    if ans[N-1] == 'S' and ans[N] == ans[0]:
        if ans[0] == 'S':
            if s[0] == 'o' and ans[1] == 'S':
                break
            elif s[0] == 'x' and ans[1] == 'W':
                break
        else:
            if s[0] == 'o' and ans[1] == 'W':
                break
            elif s[0] == 'x' and ans[1] == 'S':
                break
    elif ans[N-1] == 'W' and ans[N] == ans[0]:
        if ans[0] == 'S':
            if s[0] == 'o' and ans[1] == 'W':
                break
            elif s[0] == 'x' and ans[1] == 'S':
                break
        else:
            if s[0] == 'o' and ans[1] == 'S':
                break
            elif s[0] == 'x' and ans[1] == 'W':
                break
    if n == 3:
        print(-1)
        exit()
ans.pop()
ans = ''.join(ans)
print(ans)


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

#define int long long
using namespace std;
#define rep(i, n) for(int i=0;i<(n);++i)
typedef pair<int, int> pii;
const int INF = 1l << 60;

int N, K;
int A[100100];
int fac[100100];
int fac_inv[100100];
const int mod = 1000000007;

int powm(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) {
            res *= a;
            res %= mod;
        }
        b >>= 1;
        a *= a;
        a %= mod;
    }
    return res;
}

int inv(int x) {
    return powm(x, mod - 2);
}

void calc() {
    fac[0] = 1;
    for (int i = 1; i <= 100001; ++i) {
        fac[i] = fac[i - 1] * i % mod;
    }
    for (int i = 0; i <= 100001; ++i) {
        fac_inv[i] = inv(fac[i]);
    }
}

signed main() {
    calc();
    cin >> N >> K;
    rep(i, N) {
        cin >> A[i];
    }
    sort(A, A + N);

    int ans = 0;
    for (int i = N - 1; i >= K - 1; --i) {
        //Aiがmaxになる
        //i_C_(K-1)回
        ans += A[i] * fac[i] % mod * fac_inv[K - 1] % mod * fac_inv[i - K + 1] % mod;
        ans %= mod;
    }

    sort(A, A + N, greater<int>());
    for (int i = N - 1; i >= K - 1; --i) {
        ans -= A[i] * fac[i] % mod * fac_inv[K - 1] % mod * fac_inv[i - K + 1] % mod;
        ans %= mod;
    }
    ans += mod;
    ans %= mod;
    cout << ans << endl;
    return 0;
}


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


void solve(std::string S){
    if((S[0] == 'A') && (count(S.begin()+2, S.end()-1, 'C') == 1)){
        replace(S.begin(), S.end(), 'A', '\0');
        replace(S.begin(), S.end(), 'C', '\0');
        //cout << S << endl;
        for(int i = 0; i < S.size(); ++i){
            if(isupper(S[i])){
                cout << "WA" << endl;
                return;
            }
        }
        cout << "AC" << endl;
    }else{
        cout << "WA" << endl;
    }
}

int main(){
    std::string S;
    std::cin >> S;
    solve(S);
    return 0;
}


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

using namespace std;

int main(void) {
	long long N;
	cin >> N;
	vector<long long> v;
	for(int i = 0; i < 5; ++i) {
		long long t;
		cin >> t;
		v.push_back(t);
	}
	sort(v.begin(), v.end());
	long long narrowest = v[0];
	long long ans = 4;
	if(N % narrowest == 0) {
		ans += N / narrowest;
	} else {
		ans += N / narrowest + 1;
	}
	cout << ans << '\n';
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define llu unsigned long long int
#define sa(a,n,t) for(int ii=0;ii<n;ii++) scanf("%"#t"",&(a)[ii])
#define rep(i,n) for(int i=0;i<n;i++) 
#define reps(i,a,n) for(int i=a;i<n;i++) 
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define rreps(i,a,n) for(int i=n-1;i>=a;i--)
#define validl(i,a,b) ((i>=a)&&(i<=b))?1:0
#define validmat(x,y,a,b,c,d) (validl(x,a,b) && validl(y,a,b))?1:0
#define validmn(x,y,m,n) validmat(x,y,0,m,0,n)
#define valid(i,n) validl(i,0,n)
#define v(t) vector<t>
#define vv(t) vector<vector<t> >
#define mk make_pair
#define pb push_back
#define pa(a,n,t)  for(int i=0;i<n;i++) printf("%"#t"",a[i])
#define p2 pair<int,int>
#define p3 pair<p2,int>
#define fi first
#define se second
#define sd(a) scanf("%d",&a)
#define sl(a) scanf("%lld",&a)
#define pl(a) printf("%lld",a)
#define pd(a) printf("%d",a)
#define sf(a) scanf("%lf",&a)
#define pf(a) printf("%lf",a)
#define nline printf("\n")
#define ss(a) scanf("%s",a)
#define ps(a) printf("%s",a)
#define sc(a) scanf("%c",&a)
#define pc(a) printf("%c",&a)
#define mf(m,f) m.find(f)!=m.end()
#define pp3(m) cout<<m.fi.fi<<" "<<m.fi.se<<" "<<m.se<<" "
#define pp2(m) cout<<m.fi<<" "<<m.se<<" "
#define debug 0
/*v(int) adj[200001];
void dfs(int i,int p){
    rep(j,adj[i].size()){
        if(p!=adj[i][j])
            dfs(adj[i][j],i);
    }
}*/
int main()
{
  int n;
  string s;
  cin>>n;
  cin>>s;
  int a=0,b=0;
  rep(i,n){
      if(s[i]=='R') a++;
      else b++;
  }
  int c=0;
  rep(i,a){
      if(s[i]=='W') c++;
  }
  a=min(a,c);
  cout<<min(a,b)<<endl;
  
}


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

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()
#define all2(a, b) (a).begin(), (a).begin() + (b)
#define debug(vari) cerr << #vari << " = " << (vari) << endl;

int main()
{
	string s;
	vector<int> v(26, 0);
	cin >> s;

	rep(i, s.size())
	{
		v[s[i] - 'a']++;
	}
	rep(i, v.size())
	{
		if (v[i] > 1)
		{
			cout << "no" << endl;
			return (0);
		}
	}
	cout << "yes" << endl;
	return (0);
}


Measured memory_bytes: 3592
from collections import deque
n = int(input())
a = list(map(int, input().split()))

dq = deque([])
for i in range(n):
    if (i + n) % 2 == 0:
        dq.append(str(a[i]))
    else:
        dq.appendleft(str(a[i]))

print(' '.join(dq))


Measured memory_bytes: 32964
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

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

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

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

    int r = 0;
    for (int i = 1; i * i <= s; i++) {
        if (s % i == 0) {
            int p[2] = { i, s / i };
            for (int j = 0; j < 2; j++) {
                int q = p[j];

                int t = 0;
                for (int i = 0; i < n; i++) {
                    int z = a[i] % q;
                    b[i] = z;
                    t += z;
                }
                sort(b.begin(), b.end());
                t /= q;
                int v = 0;
                for (int i = 0; i < t; i++) {
                    v += q - b[n - 1 - i];
                    if (v > k) break;
                }
                if (v <= k) r = max(r, q);
            }
        }
    }

    cout << r << endl;

    //Kのほうが十分大きい場合は、
    //全体の偶奇は変わらない たとえば全体の和が奇数なら2では割れない ていうか全体の和が変わらん
    //全部0になることはないので安心
    //あまりを足すとqの倍数になっている qを引いて負にしてもそう 決まった回数で0になる

    return 0;
}

Measured memory_bytes: 256