akhauriyash/Code-Regression huggingface dataset:
//03/05/2020
#include<bits/stdc++.h>
#include<cmath>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define debug printf("Debug\n");
#define en '\n'


#define ll long long
#define ull unsigned long long

#define pi acos(-1.0)
#define mod 1000000007

#define _fastio  ios_base:: sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define in_fre  freopen("in.txt", "r", stdin);
#define out_fre freopen("out.txt", "w", stdout);

struct Node{
    ll val,pos;
};

//Algos
template<typename T> using Pbds=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

//Number Theory
template <typename T> T BigMod (T b,T p,T m){if (p == 0) return 1;if (p%2 == 0){T s = BigMod(b,p/2,m);return ((s%m)*(s%m))%m;}return ((b%m)*(BigMod(b,p-1,m)%m))%m;}
template <typename T> T ModInv (T b,T m){return BigMod(b,m-2,m);}
template <typename T> T gcd(T a,T b){if(a<0)return gcd(-a,b);if(b<0)return gcd(a,-b);return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a,T b) {if(a<0)return lcm(-a,b);if(b<0)return lcm(a,-b);return a*(b/gcd(a,b));}

//Geometry
template <typename T> T Dis(T x1,T y1,T x2, T y2){return sqrt( SQR(x1-x2) + SQR(y1-y2) );}
template <typename T> T Angle(T x1,T y1,T x2, T y2){ return atan2( double(y1-y2) , double(x1-x2));}


/*Containers*/
vector<ll>v;
deque<ll>dq;
stack<ll>stk;
map<ll,ll>mp;
unordered_map<ll,ll>ump,ump2;
set<ll>st;
multiset<ll>mst;
unordered_set<ll>ust;
unordered_multiset<ll>umst;
priority_queue<ll,deque<ll>,greater<ll>>pq;
Pbds<ll>ost;

ll g(ll n){
    return n*n*n*n*n;
}


int main(){
    _fastio
    ll cnt=0;
    for(ll i=0;;i++){
        ll y=g(i);
        ump[y]=-1;
        ump[-y]=-1;
        ump2[y]=i;
        ump2[-y]=-i;
        v.emplace_back(g(i));
        v.emplace_back(-g(i));
        if(y>=1e18) break;

    }

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

    ll x;
    cin>>x;

    ll a,b;

    for(ll i=0;i<v.size();i++){
        ll y=v[i];
        if(ump[y+x]==-1){
            cout<<ump2[y+x]<<' '<<ump2[y]<<en;
            return 0;
        }
        else if(ump[y-x]==-1){
            cout<<ump2[y]<<' '<<ump2[y-x]<<en;
            return 0;
        }
    }




    return 0;
}


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

using namespace std;

#ifdef KACTL
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define sz(x) (int)(x).size()
#endif
#define all(x) begin(x), end(x)

using ll = int64_t;
using ld = long double;
using pii = pair<int32_t, int32_t>;
using vi = vector<int32_t>;

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int h, w, a, b;
    cin >> h >> w >> a >> b;

    /* h = w, a = b
     * do the jagged thing
     *
     * XX.
     * .XX
     * X.X
     *
     * XX..
     * .XX.
     * ..XX
     * X..X
     *
     *
     * some can be 1s and some can be zeros
     * 2 4 1 1
     *
     * 3 3 1 1
     */

    vector<string> res(h, string(w, '0'));
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            res[i][j] ^= (i < b) ^ (j < a);
        }
    }

    for (auto& row : res)
        cout << row << '\n';

    return 0;
}


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

int main(){
  int n, c;
  c = 0;
  cin >> n;
  vector<int> vec(n);
  for(int i = 0; i < n; i++) {
    cin >> vec.at(i);
  }
  for(int i = 0; i < n; i++){
    if(i % 2 == 1){
      continue;
    }
    if(vec.at(i) % 2 == 1) {
      c++;
    }
  }
  cout << c << endl;
}

Measured memory_bytes: 3604
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(true){
        int num = sc.nextInt();
        if(num == 0) break;
        int[] array = new int[num];
        int sum = 0;
        for(int i = 0; i < num; i++){
            array[i] = sc.nextInt();
            sum += array[i];
        }
        double a = 0;
        for(int i = 0; i < num; i++){
            a += Math.pow(array[i] - sum / (double)num, 2);
        }
        a = a / (double)num;
        
        System.out.println(Math.sqrt(a));
        }
    }
}


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

int kaifuku(vector<int> &oishisa, int x, int N) {
  int j;
  int ret=0;
  if (N-1 == x) {
  	return ret;
  }
  for (j=x+1;j<N;j++){
  	ret+=oishisa.at(x)*oishisa.at(j);
  }
  return ret;
}

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

  vector<int> oishisa(N);
  for (int i = 0; i < N; i++) {
    cin >> oishisa.at(i);
  }

  int result=0;
  for (int i = 0; i < N; i++) {
    result+=kaifuku(oishisa,i,N);
  }
  cout << result << endl;
}


Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main( )
{	
    int n;
    
    cin>>n;
    
    int maxProfit = 1-1000000000;
    int Rj, Ri;
    cin>>Ri;
    n--;
    while( n-- ) {
    	cin>>Rj;
       	maxProfit = max( maxProfit, Rj - Ri  );
    	Ri = min( Ri, Rj );
    }
    cout<<maxProfit<<endl;
	
	return 0;
}

Measured memory_bytes: 1164
n,m=map(int,input().split())
lst=[]
for i in range(m):
    lst.append(list(map(int,input().split())))

front=[]
back=[]

for i in lst:
    if i[0]==1:
        front.append(i[1])

for i in lst:
    if i[1]==n:
        back.append(i[0])
front=set(front)
back=set(back)
print("POSSIBLE" if len(front&back)>=1 else "IMPOSSIBLE")

Measured memory_bytes: 142160
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

int main() {
	ll n;
	cin>>n;
	ll ch[10000100];
	for(ll i=1;i<=n;i++){
		ch[i]=1;
	}
	for(ll i=2;i<=n;i++){
		ll now=1;
		while((now)*i<=n){
			ch[now*i]++;
		//	cout <<now*i<<endl;
			now++;
		}
	}
	ll ans=0;
	for(ll i=1;i<=n;i++){
		ans+=i*ch[i];
	}
	cout <<ans;
	// your code goes here
	return 0;
}

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


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

    vector<int> d(M - 1);
    for (int i = 0; i < M-1; ++i)
        d[i] = X[i + 1] - X[i];

    sort(d.rbegin(), d.rend());

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

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define ll long long                                    // long long省略
#define pb push_back                                    // push_back省略
#define mp make_pair                                    // make_pair省略
#define fi first                                        // first省略
#define se second                                       // second省略
#define itn int                                         // int誤字保険                                   // cout誤字保険
#define vecotr vector                                   // vector誤字保険
#define ednl endl                                       // endl誤字保険
#define opt() cin.tie(0); ios::sync_with_stdio(false)   // 入出力速度改善

#define rep(i,l,r) for(ll i=(l);i<(r);i++)               // 範囲[l, r)で刻み1のfor文(順方向)
#define repp(i,l,r,k) for(ll i=(l);i<(r);i+=(k))         // 範囲[l, r)で刻みkのfor文(順方向)
#define rrep(i,l,r) for(ll i=(r-1);i>=(l);i--)           // 範囲[l, r)で刻み1のfor文(逆方向)
#define rrepp(i,l,r,k) for(ll i=(r-1);i>=(l);i-=(k))     // 範囲[l, r)で刻みkのfor文(逆方向)
#define all(x) (x).begin(), (x).end()                   // vectorのポインタ位置指定用
#define max(p,q)((p)>(q)?(p):(q))                       // max拡張
#define min(p,q)((p)<(q)?(p):(q))                       // min拡張
#define bit(n,m)(((n)>>(m))&1)                          // 変数nのm番目のbitを取り出す

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int dy[]={0, 1, 0, -1};                                 // 4方向近傍
int dx[]={1, 0, -1, 0};                                 // 4方向近傍

#define INF ((1LL<<62)-(1LL<<31))
//#define MOD 998244353
#define MOD 1000000007
#define invp(a,p) pom(a,p-2,p)

////////////////////////////////////////////////////////////////////////////////////////
int main(){
	ll n, k; cin >> n >> k;
	double res = 0;
	// サイコロを振ってk以上が出た場合
	if(n >= k)
		res += double( (n - k + 1) ) / double( n );
  	//cout << res << endl;
	rep(i,1,min(n+1,k)){
		ll tmp = i, cnt = 0;
		while(tmp < k){
			tmp *= 2;
			cnt++;
		}
      	//cout << cnt << " " << pow(0.5, cnt) / n << ednl;
		res += pow(0.5, cnt) / n;
	}
	cout << fixed << setprecision(12) << res << endl;
}

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

int main(){
	int n, max_i, max_cnt1, max_cnt2, res;
	vector<int> cnt_value1(100001);
	vector<int> cnt_value2(100001);
	cin >> n;
	vector<int> v1(n/2);
	vector<int> v2(n/2);
	for(int i=0; i<n; i++){
		if(i%2==0) cin >> v1[i/2];
		else cin >> v2[i/2];
	}

	for(int i=0; i<n/2; i++){
		cnt_value1[v1[i]]++;
		cnt_value2[v2[i]]++;
	}

	max_cnt1 = 0;
	for(int i=0; i<100001; i++){
		if(max_cnt1 < cnt_value1[i]){
			max_cnt1 = cnt_value1[i];
			max_i = i;
		}
	}
	max_cnt2 = 0;
	for(int i=0; i<100001; i++){
		if(i == max_i) continue;
		if(max_cnt2 < cnt_value2[i]){
			max_cnt2 = cnt_value2[i];
		}
	}
	res = n - max_cnt1 - max_cnt2;

	max_cnt2 = 0;
	for(int i=0; i<100001; i++){
		if(max_cnt2 < cnt_value2[i]){
			max_cnt2 = cnt_value2[i];
			max_i = i;
		}
	}
	max_cnt1 = 0;
	for(int i=0; i<100001; i++){
		if(i == max_i) continue;
		if(max_cnt1 < cnt_value1[i]){
			max_cnt1 = cnt_value1[i];
		}
	}
	res = min(res, n - max_cnt1 - max_cnt2);

	cout << res << endl;
	return 0;
}

Measured memory_bytes: 1408
#define _CRT_SECURE_NO_WARNINGS
#include"bits/stdc++.h"
#define INF          1e9
#define INFLL        1e18
#define EPS          1e-9
#define MOD          1000000007
#define REP(i,n)     for(ll i=0,i##_len=(n);i<i##_len;++i)
#define REP1(i,n)    for(ll i=1,i##_len=(n);i<=i##_len;++i)
#define REPR(i,n)    for(ll i=(n)-1;i>=0;--i)
#define REPR1(i,n)   for(ll i=(n);i>0;--i)
#define REPC(i,obj)  for(auto i:obj)
#define ALL(obj)     (obj).begin(),(obj).end()
#define SETP(n)      cout<<fixed<<setprecision(n)
#define DELNL        cin.ignore(numeric_limits<streamsize>::max(),'\n')
#define VV(T,h,w)    vector<vector<T>>(h,vector<T>(w))
#define VVI(T,h,w,i) vector<vector<T>>(h,vector<T>(w,i))
using namespace std;
using ll = long long;
template<typename T = ll>inline T in() { T ret; cin >> ret; return ret; }

int main()
{
    ll h = in(), w = in();
    vector<string>m(h + 2, string(w + 2, '.'));
    REP1(i, h)m[i] = '.' + in<string>() + '.';
    REP1(i, h) {
        REP1(j, w) {
            if (m[i][j] == '#') {
                if (
                    m[i + 1][j] != '#' &&
                    m[i - 1][j] != '#' &&
                    m[i][j + 1] != '#' &&
                    m[i][j - 1] != '#'
                    ) {
                    cout << "No" << endl;
                    return 0;
                }
            }
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <map>
#include <queue>
#include <vector>
#include <cstdlib>
#define mp make_pair
#define pb push_back
#define mem(i,a) memset(i,a,sizeof(i))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
const int DMAX=200000+5;
const int MOD=1000000000+7;
template<class T> inline void read(T &x){
	x=0;
	T f=1;
	char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-'){
			f=-1;
		}
		ch=getchar();
	}
	while(ch<='9' && ch>='0'){
		x=x*10+(ch-'0');
		ch=getchar();
	}
	x*=f;
}
int pre[DMAX],suf[DMAX];
int maxn[DMAX],pol[DMAX];
int n,c,k;
bool b[DMAX];
char s[DMAX];
int main()
{
	read(n),read(k),read(c);
	scanf("%s",s+1);
	for(int i=1;i<=n;i++){
		if(s[i]=='x'){
			b[i]=0;
		}
		else{
			b[i]=1;
		}
	}
	for(int i=1;i<=n;i++){
		maxn[i]=maxn[i-1];
		pre[i]=pre[i-1];
		if(i>maxn[i] && b[i]){
			pre[i]++;
			maxn[i]=i+c;
		}
	}
	pol[n+1]=n+1;
	for(int i=n;i>=1;i--)
	{
		pol[i]=pol[i+1];
		suf[i]=suf[i+1];
		if(i<pol[i] && b[i]){
			suf[i]++;
			pol[i]=i-c;
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(pre[i-1]+suf[max(i+1,maxn[i-1]+1)]<k){
			cout<<i<<endl;
		}
	}
	return 0;
}


Measured memory_bytes: 4992
#include<stdio.h>

int main(void){
    int n;
    int x=0;
    scanf("%d",&n);
    float a;
    int b;
    for(int i=0;i<n;i++){
        scanf("%d",&b);
        a=b;
        for(int t=2;t<=a;t++){
            if(b%t==0){
                if(t>=a){
                    x++;
                }
                break;
            }
            a=b/t;
            if(t>=a){
                x++;
            }
        }
    }
    printf("%d\n",x);
    
    return 0;
}


Measured memory_bytes: 1980
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <cstring>
#include <stdlib.h>
#include <utility>
#include <set>
#include <map>
#include <string.h>
#include <cstring>

using namespace std;

int main(){
    
    int n;
    cin >> n;
    char s[100];
    char t[100];
    cin >> s >> t;
    
    for(int i=0;i<n;i++){
        cout << s[i] << t[i];
    }
    
    
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
    string s,s1;
    char ch;
    cin>>s>>s1;
    ch = s1[s1.size()-1];

    s += ch;

    if(s==s1)
    {
        cout<<"Yes\n";
    }
    else
    {
        cout<<"No\n";
    }

}


Measured memory_bytes: 3620
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<climits>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<bitset>
#include<iomanip>
using namespace std;

#define rep(i,j,n) for(int i=(j);i<(n);i++)
#define erep(i,j,n) for(int i=(j);i<=(n);i++)
#define all(i) i.begin(),i.end()
#define rall(i) i.rbegin(),i.rend()
#define INF 1e9
const int mod = 1e9+7;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef pair<int, int> pi;
typedef long long i64;

int main() {
  string s;
  cin >> s;
  string t = "CODEFESTIVAL2016";
  int cou = 0;
  rep(i, 0, 16){
    if(s[i] != t[i]) cou++;
  }
  cout << cou << endl;
}


Measured memory_bytes: 256
n=int(input())
p=[int(x) for x in input().split()]
s=[1 if i+1==element  else 0 for i,element in enumerate(p)]
ans=0
for i in range(n):
    if s[i]==1:
        ans+=1
        if i!=n-1:
            s[i+1]=0
print(ans)

Measured memory_bytes: 57132
#include<bits/stdc++.h>
#define dump(a) cout << #a << "=" << a << endl
using namespace std;


struct Point {
	int w;
	int h;
	int taikaku;

	bool operator<( const Point &right ) const {
		if (taikaku == right.taikaku) {
			return h < right.h;
		}
		else {
			return taikaku < right.taikaku;
		}
	}
};

vector<Point> points;

int main() {
	int H,W;

	for(int y = 0; y < 150; y++) {
		for(int x = 0; x < 150; x++) {
			int xx = x+1;
			int yy = y+1;
			//dump(xx);
			//dump(yy);
			if (xx > yy) {
				Point p;
				p.w = xx;
				p.h = yy;
				p.taikaku = xx*xx + yy*yy;
				points.push_back(p);
			}
		}
	}
	//dump(points.size());

	sort(points.begin(), points.end());
	/*
	for(int i = 0; i < points.size(); i++) {
		cout << points[i].taikaku << " ";
	}
	cout << endl;
	*/

	while(cin >> H >> W) {
		if (H == 0 && W == 0) { break; }
		Point ans_p;
		int taikaku = H*H+W*W;
		//dump(points.size());

		for(int i = 0; i < points.size(); i++)
		{
			//cout << points[i].h << " " << points[i].w << endl;
			if (points[i].w == W && points[i].h == H) {
				ans_p = points[i+1];
				break;
			}
		}
		cout << ans_p.h << " " << ans_p.w << endl;
	}

	return EXIT_SUCCESS;
}

Measured memory_bytes: 1348
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)

const int MOD = 1000000007;

const int INF_32 = 1LL << 30;
const int64_t INF_64 = 1LL << 60;

int main()
{
    int r;
    cin >> r;
    cout << 3 * r * r << endl;
}

Measured memory_bytes: 256
#![allow(non_snake_case)]

use std::cmp::*;

fn read_line() -> String {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

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

fn read_int_tuple() -> (i32, i32) {
    let v: Vec<i32> = read_vec();
    (v[0], v[1])
}

fn main() {
    let (N, M) = read_int_tuple();
    let mut max_L = 0;
    let mut min_R = N+1 as i32;
    for i in 0..M as usize {
        let (L, R) = read_int_tuple();
        max_L = max(max_L, L);
        min_R = min(min_R, R);
    }
    println!("{}", max(0, min_R-max_L+1));
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define ull unsigned long long int
#define exit return 0
#define boost ios_base::sync_with_stdio(0)
#define boost1 cin.tie(0)
#define boost2 cout.tie(0)
int main()
{
    boost;
    boost1;
    boost2;

    int n;
    cin>>n;

    for(int i=1;i<=9;i++)
    {
        for(int j=1;j<=9;j++)
        {
            if(i*j==n)
            {
               cout<<"Yes"<<endl;
               exit;
            }
        }
    }
    cout<<"No"<<endl;
   exit;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
#define rep(i,n) for (ll i=0;i<(n);++i)
#define rep2(i,a,b) for (ll i=(a);i<(b);++i)
#define debug(x) cout << #x << '=' << x << endl
#define all(v) (v).begin(),(v).end()
const ll MOD=1e9+7;
//const ll MOD=998244353;
const ll INF=1e9;
const ll IINF=1e18;
const double EPS=1e-8;
const double pi=acos(-1);

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(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int H,W; cin >> H >> W;
    vector<string> f(H);
    rep(i,H) cin >> f[i];
    int dh[4]={1,0,-1,0};
    int dw[4]={0,1,0,-1};
    int ans=0;
    rep(i,H){
        rep(j,W){
            if (f[i][j]=='#') continue;
            vector<vector<int>> d(H,vector<int>(W,-1));
            queue<Pii> que;
            que.push({i,j});
            d[i][j]=0;
            while(!que.empty()){
                Pii p=que.front(); que.pop();
                int h=p.first,w=p.second;
                rep(k,4){
                    int nh=h+dh[k],nw=w+dw[k];
                    if (nh<0||nh>=H||nw<0||nw>=W) continue;
                    if (f[nh][nw]=='#') continue;
                    if (d[nh][nw]>=0) continue;
                    d[nh][nw]=d[h][w]+1;
                    chmax(ans,d[nh][nw]);
                    que.push({nh,nw});
                }
            }
        }
    }
    cout << ans << endl;
}

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


class FactorialMod{
    void calc_inverse(){
        inverse[0] = 0;
        inverse[1] = 1;
        for(int i=2; i<=max_num; i++){
            inverse[i] = MOD-((MOD/i)*inverse[MOD%i]%MOD);
        }
    }

    void calc_factorial_inverse(){
        factorial[0] = factorial_inverse[0] = 1;
        for (int i=1; i<=max_num; i++) {
            factorial[i] = (factorial[i-1]*i)%MOD;
            factorial_inverse[i] = (factorial_inverse[i-1]*inverse[i])%MOD;
        }
    }

    public:
        int max_num;
        vector<ll> inverse; 
        vector<ll> factorial;
        vector<ll> factorial_inverse;
        FactorialMod(int _max_num){
            max_num = _max_num;
            inverse = vector<ll>(max_num+1);
            factorial = vector<ll>(max_num+1);
            factorial_inverse = vector<ll>(max_num+1);
            calc_inverse();
            calc_factorial_inverse();
        }

        ll combination(int n, int k){
            if(n<k) return 0;
            return (((factorial[n]*factorial_inverse[k])%MOD)*factorial_inverse[n-k])%MOD;
        }

        ll multiChoose(int n, int k){
            return combination(n+k-1, k);
        }
};

ll modpow(ll x, ll n, ll md=MOD){
    ll res=1, dig=x;
    while(n){
        if(n&1) res = res*dig%md;
        dig = dig*dig%md;
        n /= 2;
    }
    return res;
}


int main(){
    ll n, k;    cin >> n >> k;
    vector<ll> a(n);
    rep(i, n)   cin >> a[i];
    sort(ALL(a));
    FactorialMod calc_mod(n);
    ll res=0;
    rep(i, n){
        ll dif = (calc_mod.combination(i, k-1)-calc_mod.combination(n-i-1, k-1)+MOD)%MOD;
        res += (dif*a[i]%MOD);
        res = (res+MOD)%MOD;
        //cout << res << ' ';
        //cout << calc_mod.combination(i, k-1) << ' ' << calc_mod.combination(n-i-1, k-1) << endl;
    }
    cout << res << endl;
}


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

using namespace std;

int main(void)
{
  string s;

  cin >> s;

  if (s[1] == s[2]) {
    if (s[0] == s[1] || s[2] == s[3]) {
      cout << "Yes" << endl;
      return 0;
    }
  }

  cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define SZ(x) ((int)(x).size())
typedef long long ll;
typedef long double ld;
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cout.setf(ios::fixed); cout.precision(20);
    string s; cin >> s;
    int res = 0;
    string good = "ACGT";
    int n = SZ(s);
    for (int i = 0; i < n; i++) {
        int sz = 0, j = i;
        while (j < n && count(good.begin(), good.end(), s[j])) {
            j++, sz++;
        }
        if (i == j) {
            j++;
        }
        i = j - 1;
        res = max(res, sz);
    }
    cout << res << "\n";
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
#include<cmath>
#include<bitset>
#include<queue>
#define ll long long
#define itn int
#define co(ans) cout<<ans<<endl;
#define COYE cout<<"YES"<<endl;
#define COYe cout<<"Yes"<<endl;
#define COye cout<<"yes"<<endl;
#define CONO cout<<"NO"<<endl;
#define CONo cout<<"No"<<endl;
#define COno cout<<"no"<<endl;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n)  FFOR(i,1,n)
#define SORT(V) sort((V).begin(),(V).end())
#define REVERSE(V) reverse((V).begin(),(V).end())
#define INF ((1LL<<62)-(1LL<<31))
#define MOD 1000000007
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
using namespace std;


bool primeNumber(ll n){
    if(n < 2) return false;
    else{
        for(ll i = 2; i * i <= n; i++){
            if(n % i == 0) return false;
        }
        return true;
    }
}


int main(){
  ll X;
  cin>>X;
  
  for(ll i=X; i<=2*X+100; ++i){
    if(primeNumber(i)){
      co(i);
      return 0;
    }
  }
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		char[] s = sc.next().toCharArray();
		int N = s.length;
		int P = 0;
		for(int i=0; i<N; i++)
			if(s[i]=='p')
				P++;
		
		System.out.println(N/2-P);
		
		sc.close();
	}
}


Measured memory_bytes: 13836
import java.util.*;
import java.io.*;
public class Main {
        public static void main(String[] args){
                Scanner sc = new Scanner(System.in);
                Map hs = new HashMap();
                PrintWriter ou = new PrintWriter(System.out);
                int n = Integer.parseInt(sc.next());
                int h = Integer.parseInt(sc.next());
                int[][] a = new int[2][n];
                for(int i = 0 ; i < n ; i++){
                        for(int j = 0 ; j < 2 ; j++){
                                a[j][i] = Integer.parseInt(sc.next());
                        }
                }
                for(int i = 0 ; i < 2 ; i++){
                        Arrays.sort(a[i]);
                }
                sc.close();
                int q = n - 1;
                long yono = 0;
                while(h > 0){
                        yono++;
                        if(q >= 0 && a[1][q] > a[0][n - 1]){
                                h -= a[1][q];
                                q--;
                        }else{
                                h -= a[0][n - 1];
                        }
                }
                ou.print(yono + "\n");
                ou.flush();
        }
}

Measured memory_bytes: 61524
#include <iostream>
#include <cmath>
#include <cassert>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
#include <numeric>
#include <queue>
#include <type_traits>
#include <fstream>
//#include <bits/stdc++.h>

typedef long long ll;
const ll INF = (ll)1e18 + 1;
const ll MOD = 1e9 + 7;

// print(x, y, z);
// printVec(va.begin(), va.end());
void print(){ std::cout << std::endl; }
template <typename Head> void print(Head&& head) { std::cout << head << std::endl; }
template <typename Head, typename... Tail> void print(Head&& head, Tail&&... tail)
{
  std::cout << head << " ";
  print(std::forward<Tail>(tail)...); // or print(tail...);
}
template<typename Iterator> void printVec(Iterator begin, Iterator end)
{
  for (Iterator it = begin; it != end; it++) {
    std::cout << "[" << it - begin << "] " << *it << " ";
    if ((it - begin) % 20 == 19 || it == end - 1) { std::cout << std::endl; }
  }
}
template<typename Iterator> void printVecPair(Iterator begin, Iterator end)
{
  for (Iterator it = begin; it != end; it++) {
    std::cout << "[" << it - begin << "] " << it->first << " " << it->second << " ";
    if ((it - begin) % 10 == 9 || it == end - 1) std::cout << std::endl;
  }
}

template<typename T> T bitnum(T x)
{
  T cnt = 1;
  T ret = 0;
  while (x > 0) {
    ret += (x % 2) * cnt;
    x /= 2;
    cnt *= 10;
  }
  return ret;
}

template<typename T> T lminimum(const std::vector< T >& v) {return *std::min_element(v.begin(), v.end());}
template<typename T> T lmaximum(const std::vector< T >& v) {return *std::max_element(v.begin(), v.end());}
template<typename T> void lunique(std::vector< T >& v) {v.erase(std::unique(v.begin(), v.end()), v.end());}
template<typename T> void lsort(std::vector< T >& v) {std::sort(v.begin(), v.end());}
template<typename T> void lgreatersort(std::vector< T >& v) {std::sort(v.begin(), v.end(), std::greater<>());}
template<typename T> bool lnext_permutation(std::vector< T >& v) {return std::next_permutation(v.begin(), v.end());}

int main(int argc, char* argv[])
{
  std::string s;
  std::cin >> s;

  std::string::iterator it;
  ll cnt0 = 0;
  ll cnt1 = 0;
  for (it = s.begin(); it != s.end(); it++) {
    if (*it == '0') cnt0++;
    if (*it == '1') cnt1++;
  }
  std::cout << std::min(cnt0, cnt1) * 2 << std::endl;

  return 0;
}


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

using namespace std;

#define dump(x) cerr << #x << " = " << (x) << endl;
#define PB push_back
#define MP make_pair
#define ll long long

#define FILL(ptr, value) FILL_((ptr), sizeof(ptr) / sizeof(value), (value))

template <typename T>
void FILL_(void *ptr, size_t size, T value)
{
  std::fill((T *)ptr, (T *)ptr + size, value);
}

inline int toInt(string s)
{
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}
template <class T>
inline string toString(T x)
{
  ostringstream sout;
  sout << x;
  return sout.str();
}

int dp[200002][2];
int pre[200002][2];

int main()
{
  std::ios::sync_with_stdio(false);
  string t;
  cin >> t;
  for (int i = 0; i < t.length(); ++i)
  {
    if (t[i] == 'P')
    {
      if (dp[i][0] >= dp[i][1])
      {
        dp[i + 1][0] = dp[i][0];
        pre[i + 1][0] = 0;
      }
      else
      {
        dp[i + 1][0] = dp[i][1];
        pre[i + 1][0] = 1;
      }
    }
    else if (t[i] == 'D')
    {
      int a = dp[i][0] + 2;
      int b = dp[i][1] + 1;
      if (a >= b)
      {
        dp[i + 1][1] = a;
        pre[i + 1][1] = 0;
      }
      else
      {
        dp[i + 1][1] = b;
        pre[i + 1][1] = 1;
      }
    }
    else
    {
      int a = dp[i][0];
      int b = dp[i][1];

      if (a >= b)
      {
        dp[i + 1][0] = a;
        pre[i + 1][0] = 0;
      }
      else
      {
        dp[i + 1][0] = b;
        pre[i + 1][0] = 1;
      }

      a = dp[i][0] + 2;
      b = dp[i][1] + 1;

      if (a >= b)
      {
        dp[i + 1][1] = a;
        pre[i + 1][1] = 0;
      }
      else
      {
        dp[i + 1][1] = b;
        pre[i + 1][1] = 1;
      }
    }
  }
  int cur;
  if(dp[t.length()][0] >= dp[t.length()][1])
  {
    cur = 0;
  }else{
    cur = 1;
  }

  vector<char> res;
  string pd = "PD";
  res.push_back(pd[cur]);
  for(int i=t.length()-1; i>0; --i)
  {
    cur = pre[i+1][cur];
    res.push_back(pd[cur]);
  }

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

Measured memory_bytes: 7040
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAX = 1003;
const int mod = 1e9+7;
int f[MAX][MAX];
int a[MAX][MAX];
signed main()
{
	int n,m;
	cin>>n>>m;
	char temp;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>temp;
			if(temp == '.') a[i][j] = 1;
			else a[i][j] = 0;
		}
	}
	
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(i + j != 2)
			{
				f[i][j] = ( (a[i-1][j] * f[i-1][j] % mod + a[i][j-1] * f[i][j-1] % mod) * a[i][j] )% mod;
			}
			
			else
			{
				f[i][j] = 1;
			}
		}
	}
	
	cout<<f[n][m];
}

Measured memory_bytes: 16000
from itertools import product

def main():
    s = input() 
    ans = ""
    for p in product(["+", "-"], repeat=3):
        res = ""
        for a,b in zip(s,p):
            res += a+b
        res += s[-1]
        if eval(res) == 7:
            ans = res
            break
    print(ans+"=7")


if __name__ == "__main__":
    main()

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define ALL(x) (x).begin(), (x).end()
int main() {
  string sa, sb, sc ;
  cin >> sa >> sb >> sc;
  int flag=0;
  char f;
  while(1) {
    if (flag==0) {
      f = sa.front();
      sa.substr(1);
    }

    flag++;
    if (f=='a') {
      if(sa.size() == 0) {
        cout << "A" << endl;
        break;
      }
      f = sa.front();
      sa = sa.substr(1);
    } else if (f=='b') {
      if(sb.size() == 0) {
        cout << "B" << endl;
        break;
      }
      f = sb.front();
      sb = sb.substr(1);
    } else if (f=='c') {
      if(sc.size() == 0) {
        cout << "C" << endl;
        break;
      }
      f = sc.front();
      sc = sc.substr(1);
    }
  }

  return 0;
}

Measured memory_bytes: 256
program ABC093B
	integer(8)::A,B,K,i
	integer(8)::s,e
	read(5,*)A,B,K
	
	do i=A,B
		if(i<=A+K-1)then
			print'(i0)',i
		else if(i>=B-K+1)then
			print'(i0)',i
		end if
	end do
end program ABC093B


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  string n;
  cin>>n;
  int s=0;
  for(int i=0;i<(int)n.size();i++)
    s+=(int)(n.at(i)-'0');
  cout<<(s%9==0?"Yes":"No")<<endl;
}

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

int H[100005], dp[100005];

int absdif(int a, int b)
{
    if (a >= b) return(a - b);
    return(b - a);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> H[i];
    if (N == 1)
    {
        cout << "0\n";
        return(0);
    }
    dp[N] = 0;
    dp[N - 1] = absdif(H[N - 1], H[N]);
    for (int i = N - 2; i; i--) dp[i] = min(absdif(H[i], H[i + 1]) + dp[i + 1], absdif(H[i], H[i + 2]) + dp[i + 2]);
    cout << dp[1] << '\n';
    return(0);
}

Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
using namespace std;
long long n,k,s;
int main(){
	cin>>n>>k>>s;
	if (k!=0){
		for (int i=1;i<=k;i++)cout<<s<<" ";
		if (s<100)for (int i=k;i<n;i++)cout<<s+10<<" ";
		else for (int i=k;i<n;i++)cout<<s-1<<" ";
	}else{
		if (s<100)for (int i=k;i<n;i++)cout<<s+10<<" ";
		else for (int i=k;i<n;i++)cout<<s-1<<" ";
	}
	return 0;
}



Measured memory_bytes: 1280
#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 ll long long 
#define FI first 
#define SE second
#define pb push_back 
#define eb emplace_back
#define mod 1000000007
#define all(c) (c).begin(),(c).end()
#define LB  lower_bound
#define UB  upper_bound
#define max3(a,b,c) max(c,max(a,b))
#define min3(a,b,c) min(c,min(a,b))
#define mems(s, n) memset(s, n, sizeof(s))
#define NINF -1e18
#define INF 1e18
#define int ll int
#define OOK order_of_key  //no of elements less than
#define FBO find_by_order //iterator pointing kth element;indexing starts from 0
#define CK3(x,y,z) cout<<(x)<<" "<<(y)<<" "<<(z)<<endl
#define CK4(a,b,c,d) cout<<(a)<<" "<<(b)<<" "<<(c)<<" "<<(d)<<endl

typedef pair<int,int> PII;
typedef pair<pair<int,int>,int> PPII;
typedef pair<int,pair<int,int>> PIPI;
typedef map<int,int>MII;
typedef vector<int> VI;
template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int power(int a, int b)
{int x=1,y=a;while(b>0){if(b%2){x =(x*y)%mod;}y =(y*y)%mod;b/=2;}return x%mod;}

//int modInverse(int a, int m) {return power(a, m-2);} //gcd(a,m)=1 


signed main()
{
ios::sync_with_stdio(false); cin.tie(0);
int T=1,T1=0;//cin>>T;
while(T1++<T)
{//cout<<"Case #"<<T1<<": ";
 
 int n,k;
 cin>>n>>k;VI dp(100001,0);
 int ans=0,sum=0;
 for(int i=k;i>=1;i--)
 {
     int x=k/i;
     int mn=(power(x,n)-dp[i]+mod)%mod;
     ans=(ans+mn*i)%mod;
     //sum+=mn;
     //sum%=mod;
     int aa=i;
     for(int i1=1;i1*i1<=aa;i1++)
     {
         if(aa%i1==0)
         {
             dp[i1]+=mn;
             dp[i1]%=mod;
             if(aa/i1!=i1)
             {
                 dp[aa/i1]+=mn;
                 dp[aa/i1]%=mod;
             }
         }
         
     }
 }//cout<<sum<<endl;
 //int ab=(power(k,n)-sum+mod)%mod;
 //ans=(ans+ab)%mod;
 cout<<ans<<endl;
}


return 0;
}





Measured memory_bytes: 3992
#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <cctype>
#include <cstdlib>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <list>
#include<map>
#include<set>
using namespace std;

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

Measured memory_bytes: 512
W,a,b = map(int,input().split())

if(a+W < b):
  ans = b-(a+W)
  print(ans)
elif((a<=b<=a+W)or(a<=b+W<=a+W)):
  ans = 0
  print(ans)
else:
  ans = a - (b+W)
  print(ans)
  

Measured memory_bytes: 2940
#include <iostream>
#include <math.h>
#include <iomanip>

using namespace std;

int main()
{
	double a, b, C;
	cin >> a >> b >> C;

	const double PI = acos(-1);
	double radian = C / 180.0 * PI;

	double h = b * sin(radian);
	double S = a * h * 0.5;
	double a_left = b * cos(radian);
	double a_right = a - a_left;
	double d = sqrt((a_right * a_right) + (h * h));
	double L = a + b + d;

	cout << fixed << setprecision(6) << S << endl << L << endl << h << endl;

	return 0;
}



Measured memory_bytes: 3640
N = int(input())
S = [int(input()) for k in range(N)]

if sum(S)%10==0:
    ans = 0
else:
    print(sum(S))
    exit()

for k in range(N):
    if sum(S[:k]+S[k+1:])%10==0:
        pass
    else:
        ans = max(ans,sum(S[:k]+S[k+1:]))

print(ans)

Measured memory_bytes: 3060
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}

const int dm = 1 << 21;
char dn[dm], * di = dn;
inline void putint(int X) {
	int keta = 0;
	char C[10];
	while (X) {
		*(C + keta) = '0' + X % 10;
		X /= 10;
		keta++;
	}
	for (int i = keta - 1; i >= 0; i--) *di++ = (*(C + i));
	*di++ = '\n';
}
int n;
char c[6];
inline void putsaidai() {
	for (int i = n - 1; i >= 0; i--) *di++ = c[i];
	*di++ = '\n';
}

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


	int N = getint();
	int A[200000];
	
	int saidai = 0;
	int niban = 0;
	rep(i, N) {
		A[i] = getint();
		if (niban < A[i]) {
			niban = A[i];
			if (niban > saidai) swap(niban, saidai);
		}
	}

	int kari = saidai;
	while (kari) {
		*(c + n) = '0' + kari % 10;
		kari /= 10;
		n++;
	}

	rep(i, N) {
		if (A[i] == saidai) putint(niban);
		else putsaidai();
	}

	fwrite(dn, 1, di - dn, stdout);

	Would you please return 0;
}

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

int N,M,X;
int num=0;
int C[12],A[12][12];
int dp[12];
long anss;
long ans=0;
bool visited[12];

void mnis(int X,int x){
  if(visited[x]) return;
  bool caan = true;
  for(int i=0; i<M; i++) dp[i] -= A[x][i];
  for(int i=0; i<M; i++) if(dp[i]<X) caan = false;
  if(caan){
    visited[x] = true;
    ans -= C[x];
    anss = min(anss, ans);
    for(int i=x; i<N; i++) mnis(X,i);
    for(int i=0; i<M; i++) dp[i] += A[x][i];
    visited[x] = false;
    ans += C[x];
  }else{
    for(int i=0; i<M; i++) dp[i] += A[x][i];
  }
  return;
}

int main(){
  bool able = true;
  cin >> N >> M >> X;
  for(int i=0; i<N; i++){
    cin >> C[i];
    for(int j=0; j<M; j++) cin >> A[i][j];
  }
  for(int i=0; i<M; i++) dp[i] = 0;
  for(int i=0; i<N; i++){
    for(int j=0; j<M; j++){
      dp[j] += A[i][j];
    }
  }
  for(int i=0; i<N; i++) ans += C[i];
  anss = ans;
  for(int i=0; i<M; i++) if(dp[i]<X) able = false;
  for(int i=0; i<N; i++) mnis(X,i);
  if(able) cout << anss << endl;
  else cout << "-1" << endl;
  return 0;
}


Measured memory_bytes: 3680
if isfile("mystdin.txt");mystdin=open("mystdin.txt","r");redirect_stdin(mystdin);end
pI(x)=parse(Int,x)
pM(x::Array{SubString{String},1})=map(pI,x)
function main()
  ans=0
  n=pI(readline())
  k=pI(readline())
  x=pM(split(readline()))
  for i in x
    ans+=min(abs(i-0),abs(i-k))
  end
  println(ans*2)
end
main()
if isdefined(Base, :mystdin);close(mystdin);end

Measured memory_bytes: 166108
N = int(input())

xl = []

for i in range(N):
    xl.append(list(map(int,input().split())))

itv = []

for i in range(N):
    right = xl[i][0] + xl[i][1] - 0.01 ##right
    left = xl[i][0] - xl[i][1] + 0.01 ##left   
    itv.append([right,left])
itv.sort()

ass = 0
tt = -1e10
for i in range(N):
    if tt < itv[i][1]:
        ass += 1
        tt = itv[i][0]
print(ass)

Measured memory_bytes: 39852
#include <bits/stdc++.h>
using namespace std;
long long pow(long long p,long long q,long long r){
  if(q==0)return 1;
  else if(q%2==0)return pow(p,q/2,r)*pow(p,q/2,r)%r;
  else return pow(p,q-1,r)*p%r;
}
int main() {
  long long n,m,k,mod=998244353,ans=0;
  cin>>n>>m>>k;
  long long a[n+1];
  a[1]=1;
  for(int i=2;i<n+1;i++){
    a[i]=a[i-1]*(n-i+1)%mod*pow(i-1,mod-2,mod)%mod;
  }
  for(int i=n-k;i<n+1;i++){
    ans+=m*pow(m-1,i-1,mod)%mod*a[i]%mod;
    ans%=mod;
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 5128
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] l = new int[n];
    int[] r = new int[n];
    int max = 0;
    for(int i =0; i < n; i++){
      l[i] = sc.nextInt();
      r[i] = sc.nextInt();
      max = max > r[i] ? max : r[i];
    }
    List<Integer> list = likeMake(sosuMake(max));
    for(int i = 0; i < n; i++){
      Integer lt = l[i];
      Integer rt = r[i];
      int low = Collections.binarySearch(list, lt);
      int high = Collections.binarySearch(list, rt);
      if(low < 0){
        low = ~low;
      }
      if(high < 0){
        high = ~high;
      }else{
        high++;
      }
      System.out.println(high - low);
    }
  }
  
  public static List<Integer> sosuMake(int max){
    List<Integer> list = new ArrayList<>();
    list.add(2);
    for(int i = 3; i <= max; i += 2){
      for(int j = 0; j < list.size(); j++){
        int tmp = list.get(j);
        if(tmp * tmp > i){
          list.add(i);
          break;
        }else if(i % tmp == 0){
          break;
        }
      }
    }
    return list;
  }
  
  public static List<Integer> likeMake(List<Integer> sosu){
    List<Integer> list = new ArrayList<>();
    for(int num : sosu){
      if(num == 2) continue;
      Integer tmp = (num + 1) / 2;
      if(Collections.binarySearch(sosu, tmp) >= 0){
        list.add(num);
      }
    }
    return list;
  }
}

Measured memory_bytes: 103916
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String args[]) {

        // 入力
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int m = Integer.parseInt(sc.next());
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(new int[] { Integer.parseInt(sc.next()), Integer.parseInt(sc.next()) });
        }

        // 主処理
        Comparator<int[]> comparator = new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(o1[0], o2[0]);
            }
        };
        Collections.sort(list, comparator);

        long result = 0;
        int count = 0;
        for (int i = 0; count < m; i++) {
            int num = list.get(i)[1];
            if (num <= m - count) {
                result += (long) list.get(i)[0] * num;
                count += num;
            } else {
                result += (long) list.get(i)[0] * (m - count);
                count = m;
            }
        }

        // 出力
        System.out.println(result);
        sc.close();
    }
}

Measured memory_bytes: 63076
#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
vector<int> A;

int win(vector<int> V) {
	int num[2]={};
	int odd;
	
	FORR(r,V) {
		num[r%2]++;
		if(r%2==1) odd=r;
	}
	
	if(num[0]%2==1) return 1;
	if(num[1]>1 || odd==1) return 0;
	int g=0;
	FORR(r,V) {
		if(r==odd) r--;
		g=__gcd(g,r);
	}
	FORR(r,V) r/=g;
	return win(V)^1;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	A.resize(N);
	FOR(i,N) cin>>A[i];
	
	if(win(A)) cout<<"First"<<endl;
	else cout<<"Second"<<endl;
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n';
	FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	solve(); return 0;
}


Measured memory_bytes: 10112
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <string>
// #include <bits/stdc++.h>
#define ll long long; int
#define req(i,k) for(int i = 0; i < k; i++)
using namespace std;


int main(void) {
    int n;
    cin >> n;
    vector<int> array(n);
    for(int i = 0; i < n; i++) {
        cin >> array.at(i);
    }
    int total = 0;
    sort(array.begin(), array.end(), greater<int>());
    for(int i = 0; i < n; i++) {
        if(i == 0) {
            total += array[i] / 2;
        } else {
         total += array[i];
        }
    }
    cout << total;
    return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
from decimal import Decimal
from itertools import permutations

# 整数の入力
N = int(input())

# スペース区切りの整数の入力
V = list(map(Decimal, input().split()))

result = 0

V = sorted(V)
result = V[0]

for value in V[1:]:
    result = (result + value) / 2


# 出力
print(result)


Measured memory_bytes: 5588
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ITP1_5
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                string[] strArray = Console.ReadLine().Split(' ');
                int height = int.Parse(strArray[0]);
                int width = int.Parse(strArray[1]);

                if (height == 0 && width == 0)
                {
                    break;
                }

                string text = "";
                for (int i = 0; i < width; ++i)
                {
                    text += "#";
                }

                for (int i = 0; i < height; ++i)
                {
                    Console.WriteLine(text);
                }
                Console.WriteLine();
            }
        }
    }
}

Measured memory_bytes: 5328
s = input().split()
l = 0
N = int(s[0])#１日
A = int(s[1])#ボーナス
B = int(s[2])#ほしい
W = N*7+A
if B%W == 0:
  l = B//W*7
else:
  if int(B%W) > int(N*7):
    l = (1+B//W)*7
  else:
    if int(B%W%N) == 0:
      l = B//W*7+B%W//N
    else:
      l = B//W*7+B%W//N+1
print(l)


Measured memory_bytes: 5596
#include<iostream>
#include<vector>
#include <cmath>
#include <map>
#include <algorithm>
using namespace std;
int main(void){
    int a,b;
    cin >> a>> b;
    int h1,h2;
    h1 = b-a-1;

    int ans = 0 ;
    for(int i=0;i<h1;i++){
       ans=ans+(i+1);
    }

    cout << ans-a << endl;



    return 0;
}

Measured memory_bytes: 256
/*
        karmany evadhikaras te
        ma phalesu kadacana 
        ma karma-phala-hetur bhur
        ma re sango'stv akarmani (B.G.-2.47)
 
Translation:
        Lord Krsna to Arjuna.
You have a right to perform your prescribed duty, 
but you are not entitled to the fruits of action. 
Never consider yourself the cause of the results of your activities, 
and never be attached to not doing your duty.    
*/
#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define int long long
const int N = 200005;
const ll mod = 2000000011;
#define ld long double
#define PI 3.14159265358979323846
const int X = 10000000;

void flash()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.setf(ios::fixed);
    cout.setf(ios::showpoint);
    cout.precision(20);
}

//3. Structure or classes
//3. Ends here

//1. Data structures declaration here
vector<int>Next;
//1. Ends here

//2. Extra Functions here
//2. Ends here


void solve();
int32_t main()
{
    flash();
    int t;
    t = 1;
    //cin>>t;
    for(int i=1;i<=t;i++){
        solve();
    }
    return 0;
}

void solve()
{
    string s;
    cin>>s;
    int cnt=0;
    int ans=0;
    for(int i=s.length()-1;i>=0;i--){
        if(s[i]=='W')cnt++;
        if(s[i]=='B')ans+=cnt;
    }
    cout<<ans;
    return;
}

Measured memory_bytes: 3776