akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define N 100000
typedef long long ll;
#define ALL(v) (v).begin(),(v).end()
#define SZ(x) int(x.size())
#define OUT(a) cout<<(a)<<endl
typedef pair<int,int> P;
#define INF 1000000000
const int MAX = 1000000;
const int MOD = 1000000007;


int main(){
	int n;
    string s;
    cin>>n>>s;
    bool f=false;
    if(n%2==0){
        f=true;
        REP(i,n/2){
            if(s[i]!=s[i+n/2]){
                f=false;
                break;
            }
        }
    }
    if(f)OUT("Yes");
    else OUT("No");
	return 0;
}

Measured memory_bytes: 764
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
template<class T> using vc = vector<T>;
template<class T> using vvc = vector<vector<T>>;

const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll INF = 1e16;
const ld EPS = 1e-11;
const ld PI = acos(-1.0L);
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define repr(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repe(i, l, r) for (ll i = (l); i < (r); i++)
#define reper(i, l, r) for (ll i = (r)-1; i >= (l); i--)

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; }

void init() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(15);}
//--------------------------------------------------------------------------------//

int main() {
    init();
    ll a,b,c;
    cin >> a >> b >> c;
    ll ans = 0;
    if(a%2 or b%2 or c%2){
        cout << 0 << endl;
        return 0;
    }
    else if(a==b and b==c){
        cout << -1 << endl;
        return 0;
    }

    while(a%2==0 and b%2==0 and c%2==0){
        ll ta = a, tb = b, tc = c;
        a = (tb + tc) / 2, b = (ta + tc) / 2, c = (ta + tc) / 2;
        ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
public class Main {
    private static java.util.Scanner scanner = new java.util.Scanner(System.in);

    public static void main(String[] args) {
        int n = scanner.nextInt();
        if (n % 4 == 0) {
            System.out.println("Yes");
        } else {
            for (int i = 1; i <= n / 7; i++) {
                if ((n - (i * 7)) % 4 == 0) {
                    System.out.println("Yes");
                    return;
                }
            }
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 23124
from scipy.optimize import*;from numpy import*;n=int(input());x=array([list(map(int,input().split()))for _ in range(n)])
def r(a):return((x-a)**2).sum(1).max()**.5;
print(minimize(r,[0,0],method="Nelder-Mead",tol=1e-8).fun)

Measured memory_bytes: 17464
while 1:
    n=int(input())
    if n==0:break
    ans=[0]*(n+1)**2
    for i in range(0,n):
        a,b,c,d,e,f,g,h=map(int,input().split())
        print(a*e-b*f-c*g-d*h,a*f+b*e+c*h-d*g,a*g-b*h+c*e+d*f,a*h+b*g-c*f+d*e)


Measured memory_bytes: 5600
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("unroll-loops") 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#define int long long
#define fr(i,a,b) for(int i = a ; i <= b ; ++i)
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define pb push_back
#define fst first
#define snd second
using namespace __gnu_pbds;
using ordered_set =
 tree<int, null_type,less<int>,
 rb_tree_tag,tree_order_statistics_node_update>;
//find_by_order(k):returns iterator to kth element starting from 0
//order_of_key(k):returns count of elements strictly smaller than k
typedef long long ll;typedef pair<int, int> pii;
typedef vector<int> vi;typedef long double ld;
template<class T>
using min_heap = priority_queue<T,vector<T>,greater<T>>; 
template<typename T> T gcd(T a, T b){return(b?__gcd(a,b):a);}
template<typename T> T lcm(T a, T b){return(a*(b/gcd(a,b)));}
template<class T> void re(T& x) { cin >> x; }
template<typename T> 
void remdup(vector<T>& v) {												
	sort(all(v)); v.erase(unique(all(v)), v.end());
}
template<typename T> void re(vector<T> &v) {trav(i,v) cin >> i;}
template<class H, class... T> void re(H& h, T&... t) { re(h); re(t...); }
void unsyncIO() { ios_base::sync_with_stdio(0); cin.tie(0); }
#ifdef np
#include "/home/o_o/MyCodes/pr.h"
#else
#define trace(...)
#endif

#define MOD 1000000007  


void solve(){
	int a ,b , c, d; 
	re(a,b,c,d);
	vi m = {a*c,b*d,b*c,a*d};
	cout << *max_element(all(m));
}
signed main() {
	unsyncIO();
	int tt =1 ;
	// cin >> tt;
	rep(i,0,tt) solve();













#ifdef np
	cout <<endl<<endl<< "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define loop(i,a,b) for(int i=a;i<b;i++)
#define test() int t;cin>>t;loop(test,1,t+1)
#define pb push_back
#define eb emplace_back
#define mkp make_pair
#define nl cout<<"\n"
#define sp cout<<" "
#define F first
#define S second
#define vi vector<int>
#define vl vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<pii>
#define vll vector<pll>
#define MOD 1000000007
#define all(x) x.begin(),x.end()

template<class C> void min_self( C &a, C b ){ a = min(a,b); }
template<class C> void max_self( C &a, C b ){ a = max(a,b); }

ll mod( ll n, ll m=MOD ){ n%=m,n+=m,n%=m;return n; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

unordered_map<long long, int, custom_hash> safe_map;

const int MAXN = 1e5+5;
const int LOGN = 21;
const ll INF = 1e14;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

char grid[25][25];
int h,w;

bool inside( int x, int y )
{
    if( x < 0 || x >= h || y < 0 || y >= w )
        return 0;
    return 1;
}

int bfs( int i, int j )
{
    queue<tuple<int,int,int>>q;
    tuple<int,int,int> t;
    get<0>(t) = i;
    get<1>(t) = j;
    get<2>(t) = 0;
    q.push(t);
    bool vis[25][25] = {};

    int ans = 0;
    while( !q.empty() )
    {
        int x,y,step;
        tie(x,y,step) = q.front();
        q.pop();

        if( vis[x][y] )
            continue;
        vis[x][y] = 1;
        ans = max( ans, step );

        for(int i=0;i<4;i++)
        {
            int nx = x + dx[i], ny = y + dy[i];
            if( inside(nx,ny) && grid[nx][ny] == '.' )
            {
                get<0>(t) = nx;
                get<1>(t) = ny;
                get<2>(t) = step+1;
                q.push(t);
            }
        }
    }
    return ans;
}

int main() 
{
    fastio();

    cin>>h>>w;
    for(int i=0;i<h;i++)
    {
        for(int j=0;j<w;j++)
        {
            cin>>grid[i][j];
        }
    }

    int mx = 0;
    for(int i=0;i<h;i++)
    {
        for(int j=0;j<w;j++)
        {
            if( grid[i][j] == '#' )
                continue;
            mx = max( mx, bfs(i,j) );
        }
    }
    cout<<mx,nl;


    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<int,null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define ordered_set_pair tree<pair<int,int>,null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update> 
#define ordered_set_mutiset tree<int,null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
typedef long long int ll;
typedef long double ld;
typedef unsigned long long int ull;
typedef pair<int,int> pi; 
#define PI 3.1415926535897932384
#define FOR(i,vv,n) for(int i=vv;i<n;i++)
#define FORR(i,n,vv) for(int i=n-1;i>=vv;i--)
#define ve vector 
#define maxind(v) (max_element(v.begin(),v.end())-v.begin())
#define minind(v) (min_element(v.begin(),v.end())-v.begin())
#define maxe(v) *max_element(v.begin(),v.end())
#define mine(v) *min_element(v.begin(),v.end())
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define eb emplace_back
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define mp make_pair
#define M 1000000007ll
#define INF 1000000000000000000ll
#define PRECISE cout.precision(18);
#define all(v) v.begin(),v.end()
#define BS(v,n) binary_search(all(v),n)
#define srt(v) sort(v.begin(),v.end())
#define rsrt(v) sort(all(v),greater <ll>())
#define uni(v) v.resize(unique(all(v))-v.begin())
#define F first
#define S second
#define GET(i,p) get<p>(i)

ll maxn=365;
ll d=0;
ve <ll> c(26);
ve <ve <ll>> v(maxn,ve <ll> (26));
ve <ll> last(26,-1);
ve <ll> assigned(maxn,-2);
ll ini=0;
//ll a[26][365][2];

ll score(){
	ll sats=0;
	FOR(i,0,d){
	FOR(j,0,26){
		sats-=c[j]*(i-last[j]);
	 }
	ll take=assigned[i];
	sats+=v[i][take]+c[take]*(i-last[take]);
	last[take]=i;
	//cout<<sats<<"\n";
}
return sats;
}

pair <ll,ll> fun1(ll da,ll q){

ll x1=-1,x2=d;
FORR(i,da,0)
if(assigned[i]==q){
	x1=i;
	break;
}
FOR(i,da+1,d)
if(assigned[i]==q){
	x2=i;
	break;
}
return make_pair(x1,x2);
}

ll modify(ll da,ll q){
pair <ll,ll> a1=fun1(da,assigned[da]);
pair <ll,ll> a2=fun1(da,q);
ll z=ini;
ll f=assigned[da];
z-=v[da][f];
z-=c[f]*(da-a1.F)*(a1.S-da);
z+=v[da][q];
z+=c[q]*(da-a2.F)*(a2.S-da);
return z;
}

void change(ll da,ll q){
 	assigned[da]=q;
}





int main(){

    FAST
//	PRECISE


cin>>d;
FOR(i,0,26)
cin>>c[i];

FOR(i,0,d)
	FOR(j,0,26)
		cin>>v[i][j];

ve <ll> dummy(d);
FOR(i,0,d){
dummy[i]=rand()%26;
}
assigned=dummy;
ini=score();

ve <pair <ll,ll> > check;
FOR(i,0,d)
FOR(j,0,26)
check.pb({i,j});

	
ll tot=check.size();

ll it=1000000;
ll j=0;
while(it>0){
	it--;
	j=j%tot;
	ll x1=check[j].F;
	ll x2=check[j].S;
	ll z=modify(x1,x2);
	if(z>ini){
		ini=z;
		change(x1,x2);
	}
	j++;
}


FOR(i,0,d)
cout<<assigned[i]+1<<"\n";

//cout<<ini<<endl;


return 0;
 }

Measured memory_bytes: 3900
#input of int(split by space)
def get_i()
  return gets.chomp.split(" ").map(&:to_i)
end
#input of float(split by space)
def get_f()
  return gets.chomp.split(" ").map(&:to_f)
end
#input of string(split by space)
def get()
  return gets.chomp.split(" ")
end
#input of string(split per one character)
def get_nsp()
  return gets.chomp.split("")
end
#yes or no decision
def yn_judge(bool,y="Yes",n="No")
  return bool ? y : n 
end
#create of array
def array(size1,init=nil,size2=-1)
  if size2==-1
    return Array.new(size1){init}
  else
    return Array.new(size2){Array.new(size1){init}}
  end
end

def max(a,b)
    return a>b ? a : b
end

def min(a,b)
    return a>b ? b : a
end

INF=Float::INFINITY

S=get_nsp
N=S.size
s="keyence".split("")
if S[0..6]==s or S[N-7..N-1]==s
    puts "YES"
    exit
end
flag=false
6.times do|i|
  if S[0..i]+S[N-6+i..N-1]==s
    flag=true
    break
  end 
end
puts yn_judge(flag,"YES","NO")

Measured memory_bytes: 1788
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;

int main()
{
	int n, a, x[51];
  cin>>n>>a;
  for(int i=1; i<=n; i++){
    cin>>x[i];
  }
  ll dp[51][2501][51]={};
  dp[0][0][0]=1;
  for(int i=1; i<=n; i++){
    for(int j=0; j<=2500; j++){
      for(int k=0; k<=n; k++){
        if(k<1 || j<x[i]) dp[i][j][k]=dp[i-1][j][k];
        else dp[i][j][k]=dp[i-1][j-x[i]][k-1]+dp[i-1][j][k];
      }
    }
  }
  ll ans=0;
  for(int i=1; i<=n; i++){
    ans+=dp[n][i*a][i];
  }
  cout<<ans<<endl;
	return 0;
}


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

int main() {
  int n, a;
  cin >> n >> a;
  
  if(a >= 500){
    cout << "Yes" << endl;
  }
  else if(n % 500 <= a){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
  
}


Measured memory_bytes: 256
d = int(input())
c = {}
s = []
C = list(map(int, input().split()))
for i in range(26):
    c[i] = C[i]
for i in range(d):
    s.append(list(map(int, input().split())))

t = 0
while t < 365:
    for i in range(26):
        if t < 365:
            t += 1
            print(i+1)
        else:
            break;

Measured memory_bytes: 9508
N = int(input())
a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))
c_list = list(map(int, input().split()))

b_sum = sum(b_list)

for i in range(N-1):
    diff = a_list[i+1] - a_list[i]
    if diff == 1:
        b_sum = b_sum + c_list[a_list[i]-1]
    else:
        continue
    
print(b_sum)

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

void Main (){
  
}

int main() {
  int a, b, c, d = 0;
  cin >> a;
  cin >> b >> c;
  for(; d <= c;){
  	d += a;
  	if(d >= b && d <= c){
  		cout << "OK" << endl;
        break;
  	}	
  	else if(c < d){
  		cout << "NG" << endl;
      break;
    }
  }
  
  
  Main();
}

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

typedef long long ll;

int main (void) {
  ios::sync_with_stdio(false);cin.tie(0);
  int n, res = 0;
  ll d;
  cin >> n >> d;
  d *= d;
  for (int i = 0; i < n; i++) {
    ll x, y;
    cin >> x >> y;
    if (x * x + y * y <= d)
      res++;
  }
  cout << res << '\n';
  return 0;
}



Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n);i++)
#define sz(x) int(x.size())
typedef unsigned long long ll;
typedef long double ld;
typedef pair<int,int> P;
constexpr int INF = 1e9;
constexpr int mod = 1e9+7;
typedef tuple<int,int,int> TP;
template <typename T>
struct FenwickTree {  
  int n;
  vector<T> data;

  FenwickTree (int sz, T init = 0) {
    n = sz;
    data.assign(n + 1, init);
  }
  //1-indexed
  void add(int k, T x) {
    for (int i = k; i <= n; i += i & -i) {
      data[i] += x;
    } 
  }

  // [0, k + 1)
  T sum (int k) {
    T res = 0;
    for (int i = k; i > 0; i -= i & -i) res += data[i];
    return res;
  }
  // [l, r);
  T get (int l, int r) {
    T res = 0;
    return sum(r - 1) - sum(l - 1);
  }

  T lower_bound(T v) {
    if (v <= 0) return 0;
    T l = 0, r = 1;
    while (r < n) r <<= 1;
    for (; r > 0; r >>= 1) {
      if (l + r <= n && data[l + r] < v) {
        v -= data[l + r];
        l += r;
      }
    }
    return l + 1;
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, q;
  cin >> n >> q;
  vector<int> c(n);
  rep(i,n) cin >> c[i], c[i]--;
  vector<TP> query;
  rep(i,q) {
    int a, b;
    cin >> a >> b;
    query.emplace_back(b, a, i);
  }
  vector<int> last(n, -1);
  FenwickTree<int> bit(n + 2);
  sort(query.begin(), query.end());
  int pr = 0;

  pr = get<0>(query.front());
 
  for (int i = 1; i <= pr; i++) {
    last[c[i - 1]] = i;
  }
  
  for (int i = 0; i < n; i++) {
    if (last[i] == -1) continue;
    bit.add(last[i], 1);
  }

  vector<int> res(q, -1);
  
  for (int i = 0; i < q; i++) {
    int l, r, id;
    tie(r, l, id) = query[i];
    
    for (int j = pr; j <= r; j++) {
      if (last[c[j - 1]] != -1) bit.add(last[c[j - 1]], -1);
      last[c[j - 1]] = j;
      bit.add(last[c[j - 1]], 1);
    }
    res[id] = bit.get(l, r + 1);
    pr = r;
  }
  
  for (auto e : res) cout << e << "\n";
  return 0;
}

Measured memory_bytes: 17384
#define _USE_MATH_DEFINES
#include<iostream>
#include<algorithm>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<deque>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define vec vector
#define vll vec<ll>
#define dou(s) atof(s.c_str())
#define lon(s) atoll(s.c_str())
#define str(n) to_string(n)
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,b,a) for(ll i=b;i>=a;i--)
#define ALL(a) a.begin(),a.end()
#define rALL(a) a.rbegin(),a.rend()
#define line "\n"
#define mav(a) (*max_element(ALL(a)))
#define miv(a) (*min_element(ALL(a)))
#define vfind(a,n) (find(ALL(a),n)-a.begin())
#define prque priority_queue
#define MOD 1000000007ll
using namespace std;
void solve();
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	solve();
}

//nCk(mod p)
/*ll fac[510000], finv[510000], inv[510000];
void cmodf(ll p = MOD) {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	rep(i, 2, 510000) {
		fac[i] = fac[i - 1] * i%p;
		inv[i] = p - inv[p%i] * (p / i) % p;
		finv[i] = finv[i - 1] * inv[i] % p;
	}
}
ll cmod(ll n, ll k, ll p = MOD) {
	return fac[n] * (finv[k] * finv[n - k] % p) % p;
}*/

//最大公約数
ll gcd(ll n, ll m) {
	ll k = n % m;
	while (k != 0) { n = m; m = k; k = n % m; }
	return m;
}
ll gcd(vector<ll> a) {
	rep(i, 1, a.size()) {
		ll k = a[i - 1] % a[i];
		while (k != 0) {
			a[i - 1] = a[i];
			a[i] = k;
			k = a[i - 1] % a[i];
		}
	}
	return a.back();
}

//最小公倍数
ll lcm(ll n, ll m) {
	ll t = n * m, k = n % m;
	while (k != 0) { n = m; m = k; k = n % m; }
	return t / m;
}
ll lcm(vector<ll> a) {
	ll n;
	rep(i, 1, a.size()) {
		n = a[i - 1] * a[i];
		ll k = a[i - 1] % a[i];
		while (k != 0) {
			a[i - 1] = a[i];
			a[i] = k;
			k = a[i - 1] % a[i];
		}
		n /= a[i];
		a[i] = n;
	}
	return n;
}

//keyの小さい方から探していった時に初めてvalueがjoken以上になる時のkey（keyが増えたらvalueも増えるか同じになるとき）
ll value(ll key) {
	/*変更*/
	return 0;
}
ll mini(ll lkey, ll rkey/*ここも調べる*/, ll joken) {
	ll mkey;
	while (lkey != rkey) {
		mkey = (lkey + rkey) / 2;
		if (value(mkey) >= joken)rkey = mkey;
		else lkey = mkey + 1;
	}
	return rkey;
}

//ペア配列の整理
struct cpl {
	ll f, s;
	bool operator<(const cpl &c) const {
		return f != c.f ? f < c.f : s < c.s;
	};
};

//変数定義

//再帰関数

//アルゴリズム
void solve() {
	ll k, m, n; cin >> n;
	rep(i, 0, n) {
		cin >> k >> m;
		vll a(n, 0);
		rep(j, 0, m) {
			cin >> k;
			a[k - 1] = 1;
		}
		cout << a[0];
		rep(j, 1, n) {
			cout << " " << a[j];
		}
		cout << line;
	}
}


Measured memory_bytes: 3184
#include <bits/stdc++.h>
using namespace std;
// Macros for easier access
#define ll long long
#define endl '\n'
#define F first
#define S second
#define umap unordered_map
#define uset unordered_set
#define test ll cases; cin>>cases; for(ll testCase = 1; testCase <= cases; testCase++)
#define fill(name, val) memset(name, val, sizeof(name));
#define mop(a, op, b)    (a%mod op b%mod)%mod
#define precise fixed<<setprecision(50)
#define vll vector<ll>
#define vvll vector<vll>
#define pll pair<ll, ll>
#define get(a, n)    for(ll it = 0; it < n; it++)    cin>>a[it];
#define boost ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define debug(x) cerr << #x << " : " << (x) << endl
// Constants
#define MX 100001
#define mod 1000000007LL
#define inf 1000000000000000000LL
void init(){
	boost;
	#ifndef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif
}

/*	Author: 🆉🅴🅽🅾🅻🆄🆂	*/

int main(){
	init();
	ll n, W, sumV = 0, w[101], v[101];	cin>>n>>W;
	for(ll i = 0; i < n; i++)	cin>>w[i]>>v[i];
	for(ll i = 0; i < n; i++)	sumV += v[i];
	ll dp[n+1][sumV+1];
	for(ll i = 1; i <= sumV; i++)	dp[0][i] = inf;	dp[0][0] = 0;
	for(ll i = 1; i <= n; i++){
		for(ll j = 0; j < sumV+1; j++){
			dp[i][j] = dp[i-1][j];
			if(j >= v[i-1])	dp[i][j] = min(dp[i][j], w[i-1] + dp[i-1][j-v[i-1]]);
		}
	}
	ll ans = 0;
	for(ll i = 0; i < sumV+1; i++)	if(dp[n][i] && dp[n][i] <= W)	ans = i;
	cout<<ans;
}

Measured memory_bytes: 82452
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int[][][] a = new int[4][3][10];
        int n = sc.nextInt();

        for(int i=0;i<n;i++){
            int b = sc.nextInt();
            int c = sc.nextInt();
            int d = sc.nextInt();
            int v = sc.nextInt();

            a[b-1][c-1][d-1] += v; 
        }
        for(int i=0;i<4;i++){
            for(int j=0;j<3;j++){
                for(int k=0;k<10;k++){
                    System.out.print(" "+a[i][j][k]);
                }
                System.out.println();
            }
            if(i!=3) System.out.println("####################");
        }sc.close();

    }    
}


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

using namespace std;

#define pb push_back

const int N = 1e3 + 5;
int n, K, cnt[40];
long long ans, a[N];
bool used[N * N];
map<long long, int> Cnt;
vector<long long> bit[40], A;

void update (long long x, int val) {
    for (int i = 0; i < 40; ++i) if ( (x >> i) & 1) cnt[i] += val;
}

signed main () {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> K;
    for (int i = 1; i <= n; ++i) cin >> a[i], a[i] += a[i - 1];

    for (int i = 1; i <= n; ++i) {
        for (int j = i; j <= n; ++j) {
            A.pb(a[j] - a[i - 1]);
            update(a[j] - a[i - 1], 1);
            Cnt[ a[j] - a[i - 1] ] ++;
        }
    }

    sort(A.begin(), A.end() );
    A.erase(unique(A.begin(), A.end() ), A.end() );

    for (int i = 0; i < A.size(); ++i) {
        for (int j = 0; j < 40; ++j) if ( ( (A[i] >> j) & 1) == 0) {
            int tmp = Cnt[ A[i] ];
            while (tmp --) bit[j].pb(i);
        }
    }

    for (int i = 39; i >= 0; --i) if (cnt[i] >= K) {
        ans |= (1LL << i);
        for (int _ : bit[i]) if (!used[_]) {
            update(A[_], -1);
        }
        for (int _ : bit[i]) if (!used[_]) {
            used[_] = 1;
        }
    }

    cout << ans;

    return 0;
}


Measured memory_bytes: 141292
#include<bits/stdc++.h>
using namespace std;
int main(){
int N;
  cin>>N;
  vector<int64_t>A(N);
  for(int i=0;i<N;i++){
  cin>>A.at(i);
  }sort(A.begin(),A.end());
  reverse(A.begin(),A.end());
  int64_t a=0; 
  int64_t b=0;
  int sum=-1;
  for(int i=0;i<N-3;i++){
  if(A.at(i)==A.at(i+1)){
  a=A.at(i); sum=i+2;break;
  }
  }if(sum!=-1){
  for(int j=sum;j<N-1;j++)
    if(A.at(j)==A.at(j+1)){
    b=A.at(j); break;
    }
  } int64_t ans=a*b;
  cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 1024
import std.algorithm, std.container, std.conv, std.math, std.range, std.typecons, std.stdio, std.string;

auto rdsp(){return readln.splitter;}
void pick(R,T)(ref R r,ref T t){t=r.front.to!T;r.popFront;}
void readV(T...)(ref T t){auto r=rdsp;foreach(ref v;t)pick(r,v);}
void readA(T)(size_t n,ref T[]t){t=new T[](n);auto r=rdsp;foreach(ref v;t)pick(r,v);}

void main()
{
  int n; readV(n);
  int[] a; readA(n, a);
  writeln(a.reduce!max - a.reduce!min);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl "\n"
#define pb push_back
#define f(i,n) for(i=0;i<n;i++)
#define F(i,a,b) for(i=a;a<=b;i++)
#define arr(a,n) for( i=0;i<n;i++)cin>>a[i];
#define fi first
#define se second
#define mp make_pair
#define mod 1000000007
#define YES cout<<"YES"<<endl;
#define Yes cout<<"Yes"<<endl;
#define NO cout<<"NO"<<endl;
#define No cout<<"No"<<endl;
#define yes cout<<"yes"<<endl;
#define no cout<<"no"<<endl;
#define vi vector<ll>
#define ed end()
#define bg begin()
#define sz size()
#define ln length()
#define s() sort(a,a+n);
#define sr() sort(a,a+n,greater<ll>());
#define v()  sort(v.begin(),v.end());
#define vr() sort(v.begin(),v.end(),greater<ll>());
#define mod 1000000007
#define fast() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
ll gcd(ll a, ll b){if(!b)return a;return gcd(b, a % b);}
ll power(ll x,ll y,ll p){ll res=1;x%=p;while(y>0){if(y&1)res=(res*x)%p;y=y>>1;x=(x*x)%p;}return res;}
int main() {
   /* #ifndef ONLINE_JUDGE
        // for getting input from input.txt
        freopen("input.txt", "r", stdin);
        // for writing output to output.txt
        freopen("output.txt", "w", stdout);
    #endif*/
        /* 
        Ofcourse it's Hard.
        It's supposed to be Hard.
        If it's easy everyone would do it.
        HARD IS WHAT MAKES IT GREAT

        YESTERDAY U SAID TOMORROW

        SLOWLY BECOMING THE PERSON I 
        SHOULD HAVE BEEN A LONG TIME AGO

        SAME TASK CAN'T BE FOUND DIFFICULT TWICE

        BTBHWSITW

        SPRH TU KAB P

        CP IS ALL ABOUT THINKING 
        YOU HAVE MUCH MORE POTENTIAL THAN U THINK

        AJIT SHIDDAT 10

        UR DAILY ROUTINE 


        */

fast();
//ll t;cin>>t;while(t--)
{
  string s;
  cin>>s;
  ll n=s.length(),f=0,cou=0;
  if(s[0]!='A')
    f=1;
  for(int i=2;i<n-1;i++)
  {
    if(s[i]=='C')
      cou++;
    if(s[i]<97&&s[i]!='C')
      f=1;
    if(cou>1)
      f=1;
  }
  if(s[n-1]<97)
    f=1;
  if(cou==0)
    f=1;
  if(s[1]<97)
    f=1;
  if(f)
    cout<<"WA"<<endl;
  else
    cout<<"AC"<<endl;

    
}
return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
#define N 128
#define MAX_VALUE 101000
#define inf (1LL << 60)

int i,j,n,W,v[N],ans;
long long d[MAX_VALUE],w[N];
///d[i] greutatea minima ca sa ajungi la valoarea i
int main()
{
    cin >> n >> W;
    ++n;
    ++W;
    for (i = 1; i < n; ++i)
        cin >> w[i] >> v[i];
    d[0] = 0;
    for (i = 1; i < MAX_VALUE; ++i)
        d[i] = inf + 1;
    for (i = 1; i < n; ++i){
        for (j = MAX_VALUE - 1; j > -1; --j){
            if(d[j] < inf && w[i] + d[j] < W){
                d[v[i] + j] = min (d[v[i] + j],w[i] + d[j]);
                ans = max (ans,v[i] + j);
            }
        }
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define itn int

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    int as[101010] = {};
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        as[a]++;
        as[b + 1]--;
    }
    for (int i = 1; i < 101010; i++) {
        as[i] += as[i - 1];
    }
    int cnt = 0;
    for (int i = 0; i < 101010; i++) {

        if (as[i] == m )cnt++;
    }
    cout << cnt << endl;
}


Measured memory_bytes: 640
#include <iostream>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <string>
#include <cmath>
#include <cstdio>
#include <cctype>
#include <ctime>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <complex>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cwchar>
#include <cwctype>
#include <exception>
#include <locale>
#include <numeric>
#include <new>
#include <stdexcept>
#include <limits>
#include <valarray>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <list>
#include <utility>
#include <bitset>
#include <algorithm>
#include <functional>
#define rep(i, n) for(int i = 0; i < (int)(n); i ++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i ++)
#define MP make_pair
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int MOD = 1e9 + 7;

int n, m, k;

int gen_dp(int from[], int to[], int l, int r)
{
	for(int i = 0; i <= m; i ++) to[i] = 0;
	
	for(int i = 0; i <= m; i ++) for(int j = l; j <= r; j ++)
	if(i + j <= m) {
		to[i + j] += from[i];
		if(to[i + j] >= MOD) to[i + j] -= MOD;
	}
}

int dp[4002][2002];

int main()
{
	scanf("%d%d%d", &n, &m, &k);
	int len = (n + m - 1) / (k - 1), ans = 0;
	
	dp[0][0] = 1;
	for(int i = 1; i < len; i ++) gen_dp(dp[i - 1], dp[i], 0, k - 1);
	
	for(int i = 0; i < len; i ++) {
		gen_dp(dp[i], dp[len], 1, k - 1);
		
		int tot = (i + 1) * (k - 1) + 1;
		for(int j = m; j >= 0; j -= k - 1)
		if(tot - j <= n) {
			ans += dp[len][j];
			if(ans >= MOD) ans -= MOD;
		}
	}
	
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 31488
#include <iostream>
#include <string>
#include <queue>
#include <map>
using namespace std;

int main(){
  int i,j,k,n;
  string str,ans,a1,a2,a3;
  while(1){
    cin >> str;
    if(str == "0") break;
    queue <string> Q;
    map <string,int> d,f;

    a1 = "r";
    a2 = "b";
    a3 = "g";
    for(i=1;i<str.size();i++){
    a1 += "r";
    a2 += "b";
    a3 += "g";
  }

    d[str] = 0;
    Q.push(str);
    ans = "NA";

    while(!Q.empty()){
      string u,v;
      u = Q.front();
      Q.pop();
      f[u] = 1;
      if(u == a1 || u == a2 || u == a3){
	ans = u;
	break;
      }

      for(i=0;i<u.size()-1;i++){
	if(u[i] == 'r' && u[i+1] == 'g' || u[i] == 'g' && u[i+1] == 'r'){
	  v = u;
	  v[i] = v[i+1] = 'b';
	  
	  if(!f[v]){
	    d[v] = d[u] + 1;
	    Q.push(v);
	    f[v] = 1;
	  }
	}

	else if(u[i] == 'r' && u[i+1] == 'b' || u[i] == 'b' && u[i+1] == 'r'){
	  v = u;
	  v[i] = v[i+1] = 'g';

	  if(!f[v]){
	    d[v] = d[u] + 1;
	    Q.push(v);
	    f[v] = 1;
	  }
	}
	
	else if(u[i] == 'g' && u[i+1] == 'b' || u[i] == 'b' && u[i+1] == 'g'){
	  v = u;
	  v[i] = v[i+1] = 'r';
	  
	  if(!f[v]){
	    d[v] = d[u] + 1;
	    Q.push(v);
	    f[v] = 1;
	  }
	}
      }
    }
    if(ans != "NA") cout << d[ans] << endl;
    else cout << "NA" << endl;
  }
  return 0;
}

Measured memory_bytes: 2748
import sys
input = sys.stdin.readline

n, w = map(int, input().split())
item = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] + [0]*w] + [[0] + [-float("inf")]*w for _ in range(n)]
wei, val = 0, 1

for i in range(n):
    for j in range(w+1):
        if item[i][wei] <= j:
            dp[i+1][j] = max(dp[i][j], dp[i][j-item[i][wei]] + item[i][val])
        else:
            dp[i+1][j] = dp[i][j]

print(dp[n][w])


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

int main() {
  int N;
  cin >> N;
  vector<long> A(N);

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

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

  string ans = "YES"; 
  for(int i = 0; i < N - 1; ++i){
    if(A.at(i) == A.at(i + 1)){
      ans = "NO";
      break;
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define che
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define MP make_pair
#define PB push_back
#define fi first
#define se second

typedef long long LL;
typedef pair<int, int> PII;
const int N= 1e5 +10;

int n;
int digSum(int x){
	int s=0;
	for (; x; x/=10) s+=x%10;
	return s;
}
int main(){
	cin>>n;
	int ans=1e9;
	for (int i=1; i<n; i++) ans= min(ans, digSum(i)+digSum(n-i));
	cout<<ans<<endl;	
	return 0;
}

Measured memory_bytes: 256
// Problem : C - Forbidden List
// Contest : AtCoder - AtCoder Beginner Contest 170
// URL : https://atcoder.jp/contests/abc170/tasks/abc170_c
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define eb emplace_back
#define pb push_back
#define size(s) (int)s.size()
#define int long long
#define vi vector<int>
#define vs vector<string>
#define vv vector<vector<int>>
#define pii pair<int,int>
#define m_p(x,y) make_pair(x,y)
#define vp vector<pair<int,int>>
#define setbits(x) __builtin_popcountll(x)
#define f first
#define se second
#define inc(v,n,x) v.assign(n,x)
#define incd(v,n) v.resize(n)
#define iniz(n) memset(n,0,sizeof(n))
#define inin(n) memset(n,-1,sizeof(n))
#define inimi(n) memset(n,0xc0,sizeof(n))
#define inima(n) memset(n,0x3f,sizeof(n))
#define all(v) (v).begin(),(v).end()

using namespace std;

template<typename T1,typename T2>istream &operator>>(istream &is, vector<pair<T1,T2>> &v) { for (pair<T1,T2> &t : v) is >> t.f>>t.se; return is; }
template<typename T>istream &operator>>(istream &is, vector<T> &v) { for (T &t : v) is >> t; return is; }
template<typename T>ostream &operator<<(ostream &os, const vector<T> &v) { for (const T &t : v) {os << t <<" ";} os << '\n'; return os; }

double pi=acos(-1.0);
const int md=1e9+7;
const int INF=1e15;
int dx1[]={0,0,-1,1};
int dy1[]={1,-1,0,0};

template<class T>
T abst(T a)
{return a<0?-a:a;}

template<class T>
T max2(T a,T b){return a>b?a:b;}
template<class T>
T min2(T a,T b){return a<b?a:b;}

void solve()
{
int x,n;cin>>x>>n;
set<int> s;
for(int i=0;i<n;i++)
{
	int x;cin>>x;
	s.insert(x);
}
if(!s.count(x))
{
	cout<<x;
	return;
}
queue<int> q;
q.push(x-1);
q.push(x+1);
while(!q.empty())
{
	int y=q.front();
	q.pop();
	if(!s.count(y))
	{
		cout<<y;
		return;
	}
	if(y<x)
	q.push(y-1);
	else
	q.push(y+1);
}
}

int32_t main(){
ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
int t=1;
//cin>>t;
for(int i=1;i<=t;i++)
{
    solve();
}
return 0;
}


Measured memory_bytes: 3644
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <sstream>
#include <cmath>
#include <set>
#include <iomanip>
#include <deque>
#include <stdio.h>
using namespace std;

#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define RREP(i,n) for(int (i)=(int)(n)-1;i>=0;i--)
#define REMOVE(Itr,n) (Itr).erase(remove((Itr).begin(),(Itr).end(),n),(Itr).end())
typedef long long ll;

struct SCC {

    int cmp_cnt;
    vector< vector< int > > G, rev_G;
    vector< bool > used;
    vector< int > vs, cmp;
    SCC (int n) : G(n),rev_G(n),used(n),vs(n),cmp(n) {}
    
    void add_edge(int from, int to) {
        G[from].push_back(to);
        rev_G[to].push_back(from);
    }
    
    void init() {
        vs.clear();
        cmp_cnt = 0;
        fill(used.begin(),used.end(),false);
        for (int i = 0; i < G.size(); i++) {
            if(!used[i]) {
                dfs(i);
            }
        }
        fill(used.begin(),used.end(),false);
        for (int i = (int)vs.size() - 1; i >= 0; i--) {
            if (!used[vs[i]]) {
                rev_dfs(vs[i],cmp_cnt++);
            }
        }
    }
    
    void dfs(int v) {
        used[v] = true;
        for (int i = 0; i < G[v].size(); i++) {
            if (!used[G[v][i]]) dfs(G[v][i]);
        }
        vs.push_back(v);
    }
    
    void rev_dfs(int v, int k) {
        used[v] = true;
        cmp[v] = k;
        for (int i = 0; i < rev_G[v].size(); i++) {
            if (!used[rev_G[v][i]]) rev_dfs(rev_G[v][i], k);
        }
    }
    
    int size(void) {
        return cmp_cnt;
    }
    
    int operator [] (int n) {
        return cmp[n];
    }
    
};


struct SAT2 {
    
    bool satisfy;
    
    void add_closure(int a, bool sa, int b, bool sb) {
        // a^b = ~a=>b ^ ~b=>a
    }
    
    bool is_satisfay(void) {
        return satisfy;
    }
    
};


int main() {
    
    SCC inst(100010);
    int V,E; cin >> V >> E;
    REP(i,E) {
        int a,b; cin >> a >> b;
        inst.add_edge(a,b);
    }
    
    inst.init();
    

    int Q; cin >> Q;
    REP(i,Q) {
        int a,b; cin >> a >> b;
        if(inst[a] == inst[b]) {
            cout << 1 << endl;
        } else {
            cout << 0 << endl;
        }
    }
    
    return 0;
}

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

int main() {
  string s;
  cin >> s;

  ll ans = 0, cntA = 0;
  rep(i, s.size()) {
    if (s.substr(i, 2) == "BC") ans += cntA, i++;
    else if (s[i] == 'A') cntA++;
    else cntA = 0;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3724
#include <bits/stdc++.h>
using namespace std;
struct record{
	string name;
	int score;
	int id;
}arr[101];

bool cmp(record r1, record r2){
	if(r1.name.compare(r2.name) ==0) return r1.score > r2.score;
	return r1.name < r2.name;
}
void swap(record *r1, record *r2) { 
     record tmp = *r1; 
    *r1 = *r2; 
    *r2 = tmp; 
} 

void bubbleSort(record arr[], int n) { 
   int i, j; 
   for (i = 0; i < n-1; i++)       
	// Last i elements are already in place    
       for (j = 0; j < n-i-1; j++)  
           if (!cmp(arr[j],arr[j+1])) //if arr[j] not less than arr[j+1] , then swap them 
              swap(&arr[j], &arr[j+1]); 
} 
int main(){
	int n; cin>>n;
	 
	for(int i=0;i<n;i++){
		cin>>arr[i].name>>arr[i].score;
		arr[i].id = i;
	}
	//bubbleSort(arr,n);
	sort(arr,arr+n,cmp);
	for(int i=0;i<n;i++) printf("%d\n", arr[i].id+1);
	return 0;
}

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

void solve()
{
    int n,m,k,i,j,count=0,sum=0,maxi=0,mini=1e18,flag=0;
    
    
    int x;
    cin>>x>>n;
    map<int,int> mp;
    for(i=0;i<n;i++)
    {
        int a;
        cin>>a;
        mp[a]++;
    }
    
     i=0;
    while(1)
    {
        int p=x+i;
        int q=x-i;
        
        if(mp.find(q)==mp.end())
        {
            cout<<q;
            break;
        }
        if(mp.find(p)==mp.end())
        {
            cout<<p;
            break;
        }
        i++;
    }
    
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
   // cin>>t;
    while(t--)
    {
        solve();
    }
}

Measured memory_bytes: 3648
#include<bits/stdc++.h>
#include<string.h>
 
typedef long long int ll;
#define all(x) (x).begin(), (x).end()
 
using namespace std;

int nxt() {
    int x;
    cin >> x;
    return x;
}

ll nxtl(){
    ll x;
    cin>>x;
    return x;
}
 
void SieveOfEratosthenes(int n,vector <int> &primes) 
{ 
    // Create a boolean array "prime[0..n]" and initialize 
    // all entries it as true. A value in prime[i] will 
    // finally be false if i is Not a prime, else true. 
    bool prime[n+1]; 
    memset(prime, true, sizeof(prime)); 
  
    for (int p=2; p*p<=n; p++) 
    { 
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == true) 
        { 
            // Update all multiples of p greater than or  
            // equal to the square of it 
            // numbers which are multiple of p and are 
            // less than p^2 are already been marked.  
            for (int i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 
  
    // Print all prime numbers 
    for (int p=2; p<=n; p++) 
       if (prime[p]) 
          primes.push_back(p);
} 
 
ll max(ll a,ll b)
{
    if(a>b)
        return a;
    return b;
}
 
ll power(ll x, ll y,ll mod) 
{ 
    ll temp; 
    if( y == 0) 
        return 1; 
    temp = power(x, y/2,mod); 
    if (y%2 == 0) 
        return (temp*temp)%mod; 
    else
        return (((x*temp)%mod)*temp)%mod; 
}

ll f[200001];
 
ll pow(ll a, ll b, ll MOD)
{
 ll x=1,y=a; 
 while(b > 0)
    {
        if(b%2 == 1)
    {
        x=(x*y);
        if(x>MOD) x%=MOD;
    }
    y = (y*y);
    if(y>MOD) y%=MOD; 
    b /= 2;
    }
 return x;
}
 
/* Modular Multiplicative Inverse
 Using Euler's Theorem
 a^(phi(m)) = 1 (mod m)
 a^(-1) = a^(m-2) (mod m) */
ll InverseEuler(ll n, ll MOD)
{
 return pow(n,MOD-2,MOD);
}
 
ll C(ll n, ll r, ll MOD)
{
 
 return (f[n]*((InverseEuler(f[r], MOD) * InverseEuler(f[n-r], MOD)) % MOD)) % MOD;
}

ll mod=998244353;


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n=nxt(),M=nxt(),k=nxt();
    f[0] = 1;
    for(ll i = 1 ; i <= 200000 ; i++)
        f[i] = (f[i-1]*i)%mod;
    ll  ans=0;
    ll p=n-1-k;
    while(p<n)
    {
        if(p==0)
        {
            (ans+=M)%=mod;
            p++;
            continue;
        }
        ll temp=C(n-1,p,mod);
       // cout<<temp<<endl;
        (temp*=power(M-1,p,mod))%=mod;
        //cout<<temp<<endl;
        (temp*=M)%=mod;
        //cout<<p<<" "<<temp<<endl;
        (ans+=temp)%=mod;
        p++;
    }

    cout<<ans<<endl;

    
    
    
    return 0;   
}




 
 


Measured memory_bytes: 5216
#include<bits/stdc++.h>
using namespace std;
char s[2005];
int n,x,y;
int fir[2005],nxt[4005],to[4005],cnt;
int size[2005],dp[2005],add[2005],ans=1e9;

void dfs(int u,int fa){
	int A=0,B=0;
	for(int i=fir[u];i;i=nxt[i]){
		if(to[i]==fa) continue;
		dfs(to[i],u);
		add[u]+=add[to[i]];
		size[u]+=size[to[i]];
		A=max(A,dp[to[i]]);
	}
	for(int i=fir[u];i;i=nxt[i]){
		if(to[i]==fa) continue;
		if((A&1)==(add[to[i]]&1)) B+=min(A,add[to[i]]);
		else B+=min(A-1,add[to[i]]);
	}
	if(A>B-A) dp[u]=2*A-B;
	else dp[u]=B%2;
	if(s[u]=='1') size[u]++;
	if(fa!=0) dp[u]+=size[u],add[u]+=size[u];
}

int main(){
	scanf("%d",&n);
	scanf("%s",s+1);
	for(int i=1;i<n;i++){
		scanf("%d %d",&x,&y);
		to[++cnt]=y,nxt[cnt]=fir[x],fir[x]=cnt;
		to[++cnt]=x,nxt[cnt]=fir[y],fir[y]=cnt;
	}
	for(int i=1;i<=n;i++){
		memset(size,0,sizeof(size));
		memset(dp,0,sizeof(dp));
		memset(add,0,sizeof(add));
		dfs(i,0);
		if(dp[i]==0) ans=min(ans,add[i]/2);
	}
	if(ans==1e9) puts("-1");
	else printf("%d\n",ans);

	return 0;
}

Measured memory_bytes: 384
#include <stdio.h>
#include <iostream>
int main() {
    int n, count;
    int i,j;
    int x[110];
    scanf("%d", &n);

    int max = -10000, min = 10000;

    for(i = 0;i < n; i++) {
        scanf("%d", &x[i]);
        if(max <= x[i]) {
            max = x[i];
        }
        if(min >= x[i]) {
            min = x[i];
        }
    }

    int minstam = 1000000000;

    for(i = min ; i<= max; i++) {
        int stam = 0;
        for(j = 0; j < n; j++) {
            stam = stam + (x[j] - i)*(x[j] - i);
        }
        if(stam <= minstam)
            minstam = stam;
    }
    printf("%d", minstam);

    return 0;
}


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

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

pub fn read_vec2<T: std::str::FromStr>(n: usize) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

pub fn read_col<T: std::str::FromStr>(n: usize) -> Vec<T> {
    (0..n).map(|_| read()).collect()
}

fn main() {
    let nk: Vec<u64> = read_vec();
    let n = nk[0];
    let k = nk[1];

    let mut ans = 0;

    for l in k..n + 2 {
        ans = (ans + l * (n + 1 - l) + 1) % 1000000007;
    }

    println!("{}", ans);
}


Measured memory_bytes: 2096
#include <iostream>
#include <cmath>
#include <vector>
#include <time.h>
#include <map>
#include <set>
#include <deque>
#include <cstdio>
#include <cstdlib>
#include <unordered_map>
#include <bitset>
#include <algorithm>
#include <string>
#include <fstream>
#include <assert.h>
#include <list>
#include <cstring>
using namespace std;

namespace fastinput
{
	/** Interface */

	inline int readChar();
	template <class T = int> inline T readInt();
	template <class T> inline void writeInt(T x, char end = 0);
	inline void writeChar(int x);
	inline void writeWord(const char *s);

	/** Read */

	static const int buf_size = 16384;

	inline int getChar() {
		static char buf[buf_size];
		static int len = 0, pos = 0;
		if (pos == len)
			pos = 0, len = fread(buf, 1, buf_size, stdin);
		if (pos == len)
			return -1;
		return buf[pos++];
	}

	inline int readChar() {
		int c = getChar();
		while (c <= 32)
			c = getChar();
		return c;
	}

	template <class T>
	inline T readInt() {
		int s = 1, c = readChar();
		T x = 0;
		if (c == '-')
			s = -1, c = getChar();
		while ('0' <= c && c <= '9')
			x = x * 10 + c - '0', c = getChar();
		return s == 1 ? x : -x;
	}

	/** Write */

	static int write_pos = 0;
	static char write_buf[buf_size];

	inline void writeChar(int x) {
		if (write_pos == buf_size)
			fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
		write_buf[write_pos++] = x;
	}

	template <class T>
	inline void writeInt(T x, char end) {
		if (x < 0)
			writeChar('-'), x = -x;

		char s[24];
		int n = 0;
		while (x || !n)
			s[n++] = (char)('0' + x % 10), x /= 10;
		while (n--)
			writeChar(s[n]);
		if (end)
			writeChar(end);
	}

	inline void writeWord(const char *s) {
		while (*s)
			writeChar(*s++);
	}

	struct Flusher {
		~Flusher() {
			if (write_pos)
				fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
		}
	} flusher;
}

using namespace fastinput;

const int N = 1e5;

long long a[N];
long long b[N];
long long sum;

int main()
{
	long long n = readInt();
	if (n == 1)
	{
		cout << "YES";
		return 0;
	}
	for (int i = 0; i < n; ++i)
		a[i] = readInt();
	for (int i = 0; i < n; ++i)
		sum += a[i];
	long long value = n * (n + 1) / 2;
	if (sum % value != 0)
	{
		cout << "NO";
		return 0;
	}
	sum /= value;
	for (int i = 0; i < n; ++i)
	{
		b[i] = a[i] - a[(i + 1) % n] + sum;
		if (b[i] < 0 || b[i] % n != 0)
		{
			cout << "NO";
			return 0;
		}
		else
			b[i] /= n;
	}
	cout << "YES";
	return 0;
}

Measured memory_bytes: 1792
#include <stdio.h>

main(){
   int a, b;

   scanf("%d %d", &a, &b);

   if (a > b){
      printf("a > b\n");
   } else if (a < b){
      printf("a < b\n");
   } else if (a == b){
      printf("a == b\n");
   }

   return 0;
}


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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++) cin >> a[i];
    int t = 1;
    int res = -1;
    for (int i = 0; i < n + 10; i++) {
        t = a[t - 1];
        if (t == 2) {
            res = i + 1;
            break;
        }
    }
    cout << res << "\n";
    return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
typedef long long ll;
#define rep(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define REP(i,num,n) for(ll i=num, i##_len=(n); i<i##_len; ++i)
#define repprev(i,a,b) for(ll i=b-1;i>=a;i--)
#define reprev(i,n) repprev(i,0,n)
using namespace std;
#define sz(x) ((int)(x).size())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define MEMSET(v, h) memset((v), h, sizeof(v))
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 N, A;
int x[50];
ll dp[51][51][3010];
int main() {
	cin >> N >> A;
	rep(i, N) cin >> x[i];
    dp[0][0][0] = 1;
    rep(i,N){
      rep(j,N){
        rep(k,2500){
          if(dp[i][j][k]){
            dp[i + 1][j][k] += dp[i][j][k];
            dp[i + 1][j + 1][k + x[i]] += dp[i][j][k];
          }
        }
      }
    }
          ll ans = 0;
          REP(i,1,N+1) ans += dp[N][i][i*A];
          cout << ans << endl;
}


Measured memory_bytes: 58240
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, a, n) for (int i = n - 1; i >= a; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

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

  int n;
  cin >> n;
  vector<string> v(n);
  rep(i, 0, n) {
    cin >> v[i];
    sort(v[i].begin(), v[i].end());
  }

  string ans = v[0];
  int max_val = 0;
  rep(i, 1, n) {
    int nn = v[i].size();
    int c = 0, start = 0;
    string s = "";
    rep(j, 0, nn) {
      rep(k, start, ans.size()) {
        if (v[i][j] == ans[k]) {
          c++;
          s += ans[k];
          start = k + 1;
          break;
        }
      }
    }
    ans = s;
  }

  cout << ans << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
typedef struct Position{
	double x;
	double y;
}position;
void kock(int,position,position);
int main(){
	int n;
	position p1,p2;
	p1.x = 0.0;
	p1.y = 0.0;
	p2.x = 100.0;
	p2.y = 0.0;
	scanf("%d",&n);
	printf("%.8f %.8f\n",p1.x,p1.y);
	kock(n,p1,p2);
	printf("%.8f %.8f\n",p2.x,p2.y);
	return 0;
}
void kock(int n,position p1,position p2){
	position s,t,u;
	if( n==0 ) return ;
	s.x = (p1.x * 2 + p2.x * 1 ) / 3.0;
	s.y = (p1.y * 2 + p2.y * 1 ) / 3.0;
	t.x = (p1.x * 1 + p2.x * 2 ) / 3.0;
	t.y = (p1.y * 1 + p2.y * 2 ) / 3.0;
	u.x = (t.x - s.x ) / 2.0 - ( t.y - s.y ) * sqrt(3) / 2.0 + s.x;
	u.y = (t.x - s.x ) * sqrt(3) / 2.0 + ( t.y - s.y ) / 2.0 + s.y;

	kock(n-1,p1,s);
	printf("%.8f %.8f\n",s.x,s.y);
	kock(n-1,s,u);
	printf("%.8f %.8f\n",u.x,u.y);
	kock(n-1,u,t);
	printf("%.8f %.8f\n",t.x,t.y);
	kock(n-1,t,p2);
}

 

	 

Measured memory_bytes: 640
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int ans,bns;
int p[120000],q[120000];
int l[120000],r[120000];
int n,a[120000];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(i&1)p[a[i]]++;
		else q[a[i]]++;
	}
	for(int i=1;i<=100000;i++)l[i]=max(l[i-1],q[i]);
	for(int i=100000;i>=1;i--)r[i]=max(r[i+1],q[i]);
	for(int i=1;i<=n;i++){
		ans=max(ans,p[a[i]]+max(l[a[i]-1],r[a[i]+1]));
	}
	printf("%d\n",n-ans);
}

Measured memory_bytes: 2176