akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mset(x, y) memset((x), (y), sizeof(x))
#define sz(x) ((int)(x).size())

#define cerr cout
#define endl '\n'
using namespace std;

string to_string(string s) { return '"' + s + '"';}
string to_string(char s) { return string(1, s);}
string to_string(const char* s) { return to_string((string) s);}
string to_string(bool b) { return (b ? "true" : "false");}
template <typename A> string to_string(A);
template <typename A, typename B>string to_string(pair<A, B> p) {return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}
template <typename A> string to_string(A v) {bool f = 1; string r = "{"; for (const auto &x : v) {if (!f)r += ", "; f = 0; r += to_string(x);} return r + "}";}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) {cerr << " " << to_string(H); debug_out(T...);}
#define pr(...) cerr << "[" << #__VA_ARGS__ << "] :", debug_out(__VA_ARGS__)

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
const ld eps = 1e-7;
const ll mod = 1000000007;
const ll N = 998244353;

ll binpow(ll b, ll p){ ll ans = 1; while(p > 0){if(p & 1) ans = (ans * b) % mod; b = (b * b) % mod; p >>= 1;}return ans;}
ll modinv(ll x){return binpow(x, mod - 2);}

const int mxn = 2e5 + 100;
vi adj[mxn];
bool vis[mxn];
set<int> s;

void dfs(int v)
{
	vis[v] = 1;
	s.insert(v);
	for(int u : adj[v])
	{
		if(!vis[u])
			dfs(u);
	}
}

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

	int n, m, i, ans = 0, a , b;
	cin >> n >> m;
	while(m--)
	{
		cin >> a >> b;
		adj[a].eb(b);
		adj[b].eb(a);
	}
	for(i = 1; i <= n; i++)
	{
		if(!vis[i])
			dfs(i);
		ans = max(sz(s), ans);
		s.clear();
	}
	cout << ans;
}


Measured memory_bytes: 33464
#include<bits/stdc++.h>
using namespace std;
int main(void){
  int n,m;
  cin>>n>>m;
  vector<bool> tf(n);
  vector<int> num(n);
  for(int i=0;i<m;i++){
    int s,c;
    cin>>s>>c;
    if(tf[s-1] && num[s-1]!=c){
      cout<<-1<<endl;
      return 0;
    }else if(s==1 && c==0 && n!=1){
      cout<<-1<<endl;
      return 0;
    }else{
      tf[s-1]=true;
      num[s-1]=c;
    }
  }
  if(num[0]==0 && n!=1){
    num[0]=1;
  }
  for(int i=0;i<n;i++){
    cout<<num[i];
  }
  return 0;
}

Measured memory_bytes: 256
program prob3
    implicit none
    integer :: x
    integer :: tmp, ans, i

    read(*,*) x

    ans = 1
    do i = 2, 34
        tmp = i * i
        do while(tmp <= x)
            ans = max(ans, tmp)
            tmp = tmp * i
        end do
    end do

    write(*,*) ans

    stop
contains
end program prob3

Measured memory_bytes: 2828
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;
#define dame { puts("-1"); return 0;}
#define yn {puts("YES");}else{puts("NO");}
  
int main() {
  int N;
  cin >> N;
  vi A(N);
  map<int,int> mp;
  rep(i,N) {
    cin >> A[i];
    mp[A[i]]++;
  }
  int num = 0;
  int two = 0;
  for(auto m : mp) {
    num++;
    if(m.second % 2 == 0) {
      two++;
    }
  }
  if(two % 2 == 0) {
    cout << num << endl;
  } else {
    cout << num - 1 << endl;
  }
  return 0;
}

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

int main() {
  int c[3][3];
  for(int i = 0; i < 3; i++) {
    for(int j = 0; j < 3; j++) {
      cin >> c[i][j];
    }
  }
  
  int a[3], b[3];
  
  a[0] = 0;
  b[0] = c[0][0] - a[0];
  b[1] = c[0][1] - a[0];
  b[2] = c[0][2] - a[0];
  a[1] = c[1][1] - b[1];
  a[2] = c[2][1] - b[1];
  
  for(int i = 0; i < 3; i++) {
    for(int j = 0; j < 3; j++) {
      if(a[i] + b[j] != c[i][j]) {
        cout << "No" << endl;
        return 0;
      }
    }
  }
    
  cout << "Yes" << endl;
  
  return 0;
}

Measured memory_bytes: 256
n = gets.to_i
score = [0, 0]
n.times do
    cards = gets.split.map(&:to_s)
    if cards[0] > cards[1]
        score[0] += 3
    elsif cards[0] == cards[1]
        score[0] += 1
        score[1] += 1
    else
        score[1] +=3
    end
end
puts "#{score[0]} #{score[1]}"


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

int a,b=0;


bool inc(string s,string s_){
    int c=0;
	for(int i=0;i<a;i++)
		if(s[i]==s_[c])c++;
	return c==3;
}


int main(){
    string s,s_;
cin>>a;cin>>s;
for(int i=0;i<1000;i++){
	if(i<10)s_="00"+to_string(char(i));
	else if(i<100)s_="0"+to_string(char(i));
	else s_=to_string(i);
	if(inc(s,s_))b++;
}
cout<< b;
}



Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <numeric>
#include <iomanip>
#include <set>
#include <string.h>

using namespace std;

typedef long long ll;

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define REP3(i,st,en) for(ll (i)=(st);(i)<(en);(i)++)

using P = pair<ll, ll>;
const int MOD = 1e9+7;
const ll INF = 1e+14;
const double PI = 3.14159265349;

ll euclid(ll a, ll b){
  while (b>1){
    a = a % b;
    swap(a,b);
  }
  return a;
}

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

  string s;
  cin >> s;

  ll ans = 0;
  REP(i, s.length()){
    if (i%2==0){
      if (s[i]=='p'){
        ans--;
      }
    } else {
      if (s[i]=='g'){
        ans++;
      }
    }
  }

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


Measured memory_bytes: 512
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef double db;
ll N,M,D[1000],C[1000];
ll dp[1001][1001];//i city   day j night
const ll INF = 0xffffffffff;
int main()
{
	scanf("%lld%lld",&N,&M);
	for(ll i=0;i<N;i++) scanf("%lld",&D[i]);
	for(ll i=0;i<M;i++) scanf("%lld",&C[i]);
	fill(dp[1],dp[1001],INF);
	for(ll i=1;i<=N;i++){
		for(ll j=1;j<=M;j++){
			dp[i][j]=min(dp[i][j],min(dp[i][j-1],dp[i-1][j-1]+D[i-1]*C[j-1]));
		}
	}
	printf("%lld\n",dp[N][M]);
}

Measured memory_bytes: 11032
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>

using namespace std;

//typedef
typedef long long LL;
typedef vector<LL> VL;
typedef vector<VL> VVL;
typedef vector<string> VS;
typedef pair<LL, LL> PLL;

//conversion
inline LL toLong(string s) {LL v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) LL((a).size())
#define EACH(i,c) for(auto i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define UNTIL(p) while(!(p))

//constant
const double EPS = 1e-5;
const double PI  = acos(-1.0);

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

#define PUTS(x) cout << (x) << endl;

const LL INF = 10000000000000ll;

LL dp[50][2505] = {0};
bool visited[50][2505]{false};
//class Link{
//public:
//    LL to;
//    LL cost;
//    LL time;
//    Link(LL t, LL c, LL d){}
//}
vector<vector<tuple<LL,LL,LL>>> links(50);
LL c[50] = {0};
LL d[50] = {0};

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

    LL n,m,s;
    cin>>n>>m>>s;
    REP(i,m){
        LL u,v,a,b;
        cin>>u>>v>>a>>b;
        u--;
        v--;
        links[u].PB(make_tuple(v, a, b));
        links[v].PB(make_tuple(u, a, b));
    }
    REP(i,n){
        cin>>c[i]>>d[i];
    }

    REP(i,50)REP(j,2505)dp[i][j] = INF;
    s = min(s, 2500ll);
    dp[0][s] = 0;
    priority_queue<tuple<LL,LL,LL>> q;
    q.push(make_tuple(0, 0, s));
    UNTIL(q.empty()){
        auto [total_time, v, money] = q.top();
        q.pop();
        total_time = -total_time;

        if(visited[v][money])continue;
        visited[v][money] = true;

        // 交換
        {
            LL t = total_time + d[v];
            LL rest = min(money + c[v], 2500ll);
            dp[v][rest] = min(dp[v][rest], t);
            q.push(make_tuple(-t, v, rest));
        }

        // ノード遷移
        for(auto [to, cost, time] : links[v]){
            if(cost <= money){
                LL t = total_time + time;
                LL rest = money - cost;
                dp[to][rest] = min(dp[to][rest], t);
                q.push(make_tuple(-t, to, rest));
            }
        }
    }

    FOR(i,1,n){
        LL ans = INF;
        REP(j,2500){
            ans = min(ans, dp[i][j]);
        }
        PUTS(ans);
    }
}

Measured memory_bytes: 10628
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 6 + 3
def POW(x, y): return pow(x, y, MOD)
def INV(x, m=MOD): return pow(x, m - 2, m)
def DIV(x, y, m=MOD): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

def main():
    Q = II()
    query = []
    for _ in range(Q):
        query.append(LI())
    fact = [1] * MOD
    for i in range(1, MOD):
        fact[i] = fact[i - 1] * i % MOD
    ifact = [1] * MOD
    ifact[MOD - 1] = pow(fact[MOD - 1], MOD - 2, MOD)
    for i in range(MOD - 1, 0, -1):
        ifact[i - 1] = ifact[i] * i % MOD
    anss = []
    for x, d, n in query:
        if d == 0:
            ans = pow(x, n, MOD)
        else:
            x = x * pow(d, MOD - 2, MOD) % MOD
            if x + n > MOD or x == 0:
                ans = 0
            else:
                factor = pow(d, n, MOD)
                perm = fact[x + n - 1] * ifact[x - 1] % MOD
                ans = perm * factor % MOD
        anss.append(ans)
    print(*anss, sep='\n')
    return

main()

Measured memory_bytes: 108308
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using P = pair<int, int>;
using vec = vector<int>;
using mat = vector<vector<int>>;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define endl "\n"

constexpr int MOD = 1000000007;
const int INF = 1 << 30;

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

    lint res = 0;

    for (int i = 1; i <= n; i++) {
        if (i % 3 != 0 && i % 5 != 0) res += i;
    }

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

Measured memory_bytes: 3624
n, k = [int(item) for item in input().split()]

ans = 0
for b in range(1,n+1):
  if b <= k:
    continue
  ans += (b - k) * (n // b)
  if n % b >= k:
    if k != 0:
      ans += n % b - k + 1
    else:
      ans += n % b - k
print(ans)

Measured memory_bytes: 3060
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


s = readline().decode().rstrip()
t = readline().decode().rstrip()

ans = 0
for i in range(len(s)):
    if s[i] != t[i]:
        ans += 1

print(ans)

Measured memory_bytes: 9576
#include <bits/stdc++.h>
        using namespace std;
         
        int main(){
          //int a,b,c;
          string a, b, c;
          cin >> a >> b >> c;
          //cin >> s;
          //if((a+b)%2==1)cout << 1 + (a+b)/2 << endl;
          //else cout << (a+b)/2 << endl;
          cout << a.at(0) << b.at(1) << c.at(2) << endl;
          return 0;
        }

Measured memory_bytes: 256
A,B=map(int,input().split())
Adiv=[]
Bdiv=[]
Co=[]
for i in range(1,A+1):
  if A%i==0:
    Adiv+=[i]
for i in range(1,B+1):
  if B%i==0:
    Bdiv+=[i]
for i in Adiv:
  if i in Bdiv:
    Co+=[i]
M=max(Co)
print(int(A*B/M))

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

using namespace std;
using int64 = long long;

constexpr int DEBUG = 0;

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

  int a, b, c, k;
  cin >> a >> b >> c >> k;
  while (k > 0 && b <= a) {
    b *= 2;
    k--;
  }
  while (k > 0 && c <= b) {
    c *= 2;
    k--;
  }
  if (a < b && b < c) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 3648
#include <iostream>
#include <string>
#include <map>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <queue>
#include <tgmath.h>
#define MOD 1000000007
using namespace std;
#define INT_MAX 2147000000
#define LONG_MAX 9223372036854775806

typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
ll N;
ll K;
#define MAXN 200000
ll A[MAXN];
ll F[MAXN];
bool sor(int a,int b){
    if(a>b)return true;
    else return false;
}

bool ok(ll mid){
    ll kplace = K;
    for(int i=0;i<N;i++){
        if(A[i]*F[i]>mid){
            kplace -=A[i]-(mid/F[i]);
        }
        if(kplace<0){
            return false;
        }
    }
    return true;
}

void solve(){
    cin >> N >> K;
    ll sum = 0;
    rep(i,N){
        cin >> A[i];
        sum += A[i];
    }
    rep(i,N){
        cin >> F[i];
    }
    if(sum<=K){
        cout << 0 << endl;
        return;
    }
    sort(A,A+N);
    sort(F,F+N,sor);
    ll front = LONG_MAX;
    ll back = -1;
    ll mid;
    while(abs(front-back)>1){
        mid = (front+back)/2;
        //cout << mid << endl;
        if(ok(mid))front = mid;
        else back = mid;
    }
    cout << front<< endl;
}
int main(){
    solve();
    return 0;
}

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

#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define lg long long
#define db double
#define lb(x) ((x)&-(x))
#define ft first
#define sd second

#define HII cerr<<"HI"<<endl
#define LLLINE cerr<<"@@@@@@@@@@@@@@@@@@@@"<<endl

template <class _T_>
void read(_T_& d){
	d=0;int f=1;char c=getchar();
	for(;c<'0'||c>'9';c=getchar())if(c=='-')f*=-1;
	for(;c>='0'&&c<='9';c=getchar())d=d*10+c-'0';
	d*=f;
}

/************************************************/
#define MN 2005
char a[MN][MN];
int d[MN][MN];
int n,m;
int ck(int x,int y){
	return x>=0&&x<n&&y>=0&&y<m;
}
int main(){
	read(n);read(m);
	memset(d,0x3f,sizeof d);
	for(int i=0;i<n;++i){
		scanf("%s",a[i]);
	}
	queue<pii> q;
	for(int i=0;i<n;++i){
		for(int j=0;j<m;++j){
			if(a[i][j]=='#')d[i][j]=0,q.push(mp(i,j));
		}
	}
	int res=0;
	while(!q.empty()){
		int x=q.front().ft;
		int y=q.front().sd;
		q.pop();
		int D=d[x][y];
		res=max(res,D);
		if(ck(x,y-1)&&d[x][y-1]>D+1){
			d[x][y-1]=D+1;
			q.push(mp(x,y-1));
		}
		if(ck(x,y+1)&&d[x][y+1]>D+1){
			d[x][y+1]=D+1;
			q.push(mp(x,y+1));
		}
		if(ck(x-1,y)&&d[x-1][y]>D+1){
			d[x-1][y]=D+1;
			q.push(mp(x-1,y));
		}
		if(ck(x+1,y)&&d[x+1][y]>D+1){
			d[x+1][y]=D+1;
			q.push(mp(x+1,y));
		}
	}
	cout<<res;
	return 0;
}


Measured memory_bytes: 26896
#include <iostream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <algorithm>
#include <utility>
#define llint long long
#define inf 1e18
#define rep(x, s, t) for(llint (x) = (s); (x) < (t); (x)++)
#define Rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))
#define mod 998244353
using namespace std;
typedef pair<llint, llint> P;
typedef pair<P, llint> E;

llint n;
llint a[200005];

int main(void)
{
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	a[0] = -1;
	
	llint ans = 0;
	for(int i = n+1; i >= 1; i--){
		if(a[i-1] < a[i]-1){
			cout << -1 << endl;
			return 0;
		}
		if(a[i-1] > a[i]-1) ans += a[i-1];
	}
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll MOD = 1000000007;
constexpr ll INF = 1ll<<60;

int main(int argc, char **argv)
{
	string str; cin >> str;
	ll N = (ll)str.size();
	vector<ll> res(N, 0);
	for (ll i = 0; i < N;)
	{
		ll j = i + 1;
		while (j < N && str[j] == 'R') {++j;}
		ll r = j;
		while (j < N && str[j] == 'L') {++j;}
		ll rc = (r - i);
		ll lc = (j - r);
		ll s = rc + lc;
		//		std::cout << "rc : " << rc << "\tlc : " << lc << std::endl;
		if (s % 2 == 0)
		{
			res[r-1] = res[r] = s/2;
		}
		else
		{
			if (rc > lc)
			{
				if (rc & 1)
				{
					res[r-1] = s - s/2;
					res[r] = s/2;
				}
				else
				{
					res[r-1] = s/2;
					res[r] = s- s/2;
				}
			}
			else
			{
				if (lc & 1)
				{
					res[r-1] = s/2;
					res[r] = s - s/2;
				}
				else
				{
					res[r-1] = s - s/2;
					res[r] = s/2;
				}
			}
		}
		i = j;
	}

	for (ll i = 0; i < N; ++i)
		std::cout << res[i] << " ";
	std::cout << std::endl;
}


Measured memory_bytes: 1408
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        double xd = n / 1.08;
        int x1 = (int)Math.floor(xd);
        int x2 = (int)Math.ceil(xd);
        int result = -1;
        if(((int)Math.floor(x1*1.08))==n) {
            result = x1;
        }
        else if(((int)Math.floor(x2*1.08))==n) {
            result = x2;
        }
        System.out.println(result==-1?":(":result);
    }
}


Measured memory_bytes: 23508
#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<algorithm>

using namespace std;
typedef long long ll;

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

    map<string, vector<ll>> restaurants;
    map<ll, ll> point_map;

    for(ll i = 0; i < N; i++)
    {
        string S;
        ll P;
        cin >> S >> P;

        point_map.insert(make_pair(P, i));

        // 初めてのレストラン名を追加する時
        if(restaurants.count(S) == 0)
        {
            vector<ll> _P;
            _P.push_back(P);
            restaurants.insert(make_pair(S, _P));
        }
        // すでにレストラン名があった場合
        else
        {
            //cout << "aaaaaaaaaaaaaaaaaa" << endl;
            restaurants[S].push_back(P);
        }
    }

    for(auto i = restaurants.begin(); i != restaurants.end(); i++)
    {
        //cout << i->first << endl;

        vector<ll> points = i->second;

        //cout << i->first << " : " << points.size() << endl;
        sort(points.begin(), points.end(), greater<int>());

        for(ll j = 0; j < points.size(); j++)
        {
            cout << point_map[points[j]] + 1 << endl;;
        }
    }
}

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

#define rep(i, n) for(int i = 0; i < n;i++)

int main()
{
    int A, B, C, D;
    cin >> A >> B >> C >> D;
    cout << (A + B == C + D ? "Balanced" : (A + B > C + D) ? "Left" : "Right") << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){

    string s;
    cin>>s;
    if(s=="SUN"){
        cout<<7<<endl;
    }
    else if(s=="MON"){
        cout<<6<<endl;
    }
    else if(s=="TUE"){
            cout<<5<<endl;
    }
    else if(s=="WED"){
        cout<<4<<endl;
    }
    else if(s=="THU"){
        cout<<3<<endl;
    }
    else if(s=="FRI"){
        cout<<2<<endl;
    }
    else{
        cout<<1<<endl;
    }




}




Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void)
{
	int a,b,c,x;
	cin>>a>>b>>c>>x;
	int cnt=0;
	for(int i=0;i<=a;i++){
		for(int j=0;j<=b;j++){
			for(int k=0;k<=c;k++){
				if(500*i+100*j+50*k==x){
				
					cnt++;
				}
			}
		}
	}
	cout<<cnt<<endl;
	return 0;
}

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

int main(){
    unsigned long N;
    cin >> N;
    vector<unsigned long> A(N);
    for(auto& i : A)cin >> i;
    sort(A.begin(), A.end());
    unsigned long ans{0}, p{0}, b{0};
    for(const auto& i : A)if(p != i && (p = i)){
        ans += b;
        b = 1;
    }else b ^= 1;
    cout << ans + b << endl;
    return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
#include<iomanip>
#include<list>
#include<deque>
using namespace std;
//#define MODE 1
#ifdef MODE
#define DEB(X) cout<< #X <<": "<<X<<" ";
#define DEB2(X) cout<<X<<" ";
#define END cout<<endl;
#else
#define DEB(X) {}
#define DEB2(X) {}
#define END {}
#endif
typedef long long ll;
#define int ll
#define uset unordered_set
#define umap unordered_map
//typedef std::pair<int,int> P;
struct edge{int to,cost;};
const int INF=100000000000000000;
const int INF2=9223372036854775807;
const int MOD=1000000007;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define min(X,Y) (((int)(X)<(int)(Y))?(X):(Y))
#define max(X,Y) (((int)(X)>(int)(Y))?(X):(Y))
#define NP(X,Y) next_permutation(X,Y)
#define setdouble(X,Y) cout<<fixed<<setprecision(X)<<Y
int ceil2(int a,int b){if(a%b==0){return a/b;}else{return a/b+1;}}
int pow2(int a,int b){int r=1;for(int i=1;i<=b;i++){r*=a;}return r;}
int Log2(int a){int t=0;while(1){if(a==0||a==1){break;}a/=2;t++;}return t;}

int N;
string S[200010];
map<string,int> H;
vector<string> v;
int M=0;

signed main(){
	cin>>N;
	REP(i,N){
		cin>>S[i];
	}
	REP(i,N){
		H[S[i]]++;
	}
	for(auto x:H){
		M=max(M,x.second);
	}
	for(auto x:H){
		if(x.second==M){
			v.push_back(x.first);
		}
	}
	sort(v.begin(),v.end());
	REP(i,v.size()){
		cout<<v[i]<<endl;
	}
	return 0;
}


Measured memory_bytes: 28404
import sys
input = sys.stdin.readline
S = list(input())[: -1]
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mod = 10 ** 9 + 7
for i in range(len(S)):
  for j in range(13):
    for k in range(10):
      if S[i] == "?":
        dp[i + 1][(j * 10 + k) % 13] += dp[i][j]
        dp[i + 1][(j * 10 + k) % 13] %= mod
    if S[i] != "?":
      dp[i + 1][(j * 10 + int(S[i])) % 13] += dp[i][j]
      dp[i + 1][(j * 10 + int(S[i])) % 13] %= mod
print(dp[-1][5])

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

int main() {
    string s;
    cin >> s;
    if(s=="ABC") cout << "ARC" << endl;
    else cout << "ABC" << endl;
    return 0;
}

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

int main(){
  	int N;
	cin >> N;
  	int A[N];
  	for(int i = 0;i < N; i++){
    	cin >> A[i];	
    }
  	sort(A, A + N, greater<>());
  	int Alice = 0;
    int Bob = 0;
  	for(int i = 0;i < N; i++){
    	if(i == 0 || i % 2 == 0){
        	Alice += A[i];
        }else if(1 % 2 == 1){
        	Bob += A[i];
        }
    }
  	cout << Alice - Bob << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define ll long long
#define rep(i,n) for(int i = 0; i < int(n); i++)
#define vi vector<int>
#define INF (1<<30)-1
using namespace std;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
template<class T> inline bool chmax(T &a, const T &b){ if(a<b) { a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b){ if(b<a) { a=b; return 1; } return 0; }

int main(){
  cin.tie(0), ios::sync_with_stdio(false);
  int x,y,a,b,c; cin >> x >> y >> a >> b >> c;
  vi p(a),q(b),r(c);
  rep(i,a) cin >> p[i];
  rep(i,b) cin >> q[i];
  rep(i,c) cin >> r[i];
  sort(all(p),greater<int>());
  sort(all(q),greater<int>());
  // sort(all(r),greater<int>());
  priority_queue<int,vi,greater<int>> res;
  rep(i,x) res.push(p[i]);
  rep(i,y) res.push(q[i]);
  rep(i,c){
    if(res.top() < r[i]){
      res.pop();
      res.push(r[i]);
    }
  }
  ll ans = 0;
  while(!res.empty()){
    ans += res.top();
    res.pop();
  }
  cout << ans;
  cout << "\n";
  return 0;
}


Measured memory_bytes: 5412
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<map>
#include<queue>
#include<stack>
#include<deque>
#include<fstream>
#include<string>
#include<sstream>
#include<iomanip>
#include<numeric>
#include<cctype>
#include<random>
using namespace std;

//fixed << setprecision(10)
#define Yes(a) a ? "Yes" : "No";
#define YES(a) a ? "YES" : "NO";
#define rep(i,n) for(int i=0;i<n;i++)

int gcd(int a,int b) {
	if (a < b) {
		int tmp = a;
		a = b;
		b = tmp;
	}
	int r = a % b;
	while (r != 0) {
		a = b;
		b = r;
		r = a % b;
	}
	return b;
}

map<int, int> prime;
void Prime(long long int n) {
	for (int i = 2; i <= n; i++) {
		int count = 0;
		while (n % i == 0) {
			count++;
			n /= i;
		}
		if (count != 0) {
			prime.insert(make_pair(i, count));
		}
	}
}

int main() {
	long long int n, ans;
	cin >> n;
	ans = n + 1;
	for (int i = 1; i <= sqrt(n); i++) {
		if (n % i == 0) {
			 long long int a = n / i;
			if (ans - a > i) {
				ans = a + i;
			}
		}
	}
	ans -= 2;
	cout << ans << endl;
}

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

#define ll long long
#define endl "\n"

void solve(){
    ll d,t,s;
    cin >> d >> t >> s;
    if(d <= t*s){
        cout << "Yes" << endl;
        return;
    }
    cout << "No" << endl;
}

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

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

int main(){
  string S;
  cin >> S;
  int64_t Q;
  cin >> Q;
  bool flag=false;
  for(int i=0;i<Q;i++){
    int T;
    cin >> T;
    if(T==1){
      if(flag){
        flag=false;
      }else{
        flag=true;
      }
    }else{
      int F;
      cin >> F;
      char C;
      cin >> C;
      if(F==1){
        if(flag){
          S.insert(S.end(), C);
        }else{
          S.insert(S.begin(), C);
        }
      }else{
        if(flag){
          S.insert(S.begin(), C);
        }else{
          S.insert(S.end(), C);
        }
      }
    }
  }
  if(flag){
    reverse(S.begin(),S.end());
  }
  cout << S << endl;
}


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

int main() {
  int n;
  cin >> n;
  vector<int> v(n+1, 0);
  for (int i=0;i<n-1;i++) {
    int m;
    cin >> m;
    v.at(m) += 1;
  }
  for (int j=1;j<n+1;j++) {
  	cout << v[j] << endl;
  }
}

Measured memory_bytes: 4052
#include <stdio.h>
#include <stdlib.h>

int cp(const void* a, const void* b);//比較関数

int main(void){
  int i, n, d[100005];
  scanf("%d", &n);
  for(i=0; i<n;i++) scanf("%d", &d[i]);

  qsort(d, n, sizeof(int), cp);
  printf("%d\n", d[n/2] - d[-1 + n/2]);

  return 0;
}

int cp(const void* a, const void* b){
  return *(int*)a - *(int*)b;
}


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

int main(){
    int A,B;cin>>A>>B;
    if(A<=9 and B<=9)cout<<A*B;
    else cout<<-1<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef double dd;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> ii;
typedef pair<ll, int> li;
typedef pair<int, ll> il;
typedef pair<ll , ll> lli;
typedef vector<ii> vii;
typedef vector<il> vil;
typedef vector<li> vli;
typedef vector<lli> vlli;
 
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define in insert
#define f0(b) for(int i=0;i<(b);i++)
#define f00(b) for(int j=0;j<(b);j++)
#define f1(b) for(int i=1;i<=(b);i++)
#define f11(b) for(int j=1;j<=(b);j++)
#define f2(a,b) for(int i=(a);i<=(b);i++)
#define f22(a,b) for(int j=(a);j<=(b);j++)
#define sf(a) scanf("%lld",&a)
#define sff(a,b) scanf("%lld %lld", &a , &b)
#define pf(a) printf("%lld\n",a)
#define pff(a,b) printf("%lld %lld\n", a , b)
#define PI 3.14159265359
#define bug printf("**!\n")
#define mem(a , b) memset(a, b ,sizeof(a))
#define front_zero(n) __builtin_clzll(n)
#define back_zero(n) __builtin_ctzll(n)
#define total_one(n) __builtin_popcountll(n)

const ll mod = (ll)1e9+7;
const ll maxn = (ll)2e5+5;
const int nnn = 1048590;
const int inf = numeric_limits<int>::max()-1;
//const ll INF = numeric_limits<ll>::max()-1;
const ll INF = 1e18;

ll dx[]={0,1,0,-1};
ll dy[]={1,0,-1,0};
ll dxx[]={0,1,0,-1,1,1,-1,-1};
ll dyy[]={1,0,-1,0,1,-1,1,-1};


void solve(){
	ll r=0, g=0, b=0;
	ll n;
	string s;
	cin >> n >> s;
	f0(n){
		if(s[i] == 'R')r++;
		else if(s[i] == 'B')b++;
		else g++;
	}
	ll ans = 0;
	for(ll i = n-1; i >= 0; i--){
		set < char > st;
		st.in('R') , st.in('B') , st.in('G');
		if(s[i] == 'R')r--, st.erase(s[i]);
		else if(s[i] == 'B')b--,st.erase(s[i]);
		else g--,st.erase(s[i]);
		ll kr = r , kg = g , kb = b;
		for(ll j = i-1; j >= 0; j--){
			ll k = i-j;
			if(s[j] == 'R')kr--;
		    else if(s[j] == 'B')kb--;
		    else kg--;
		    if(s[i] == s[j]) continue;
		    st.erase(s[j]);
		    char bit = *st.begin();
			ll pw;
			if(bit == 'R')pw=kr;
		    else if(bit == 'B')pw=kb;
		    else pw=kg;
			if(j-k >= 0){
				if(s[j-k] == bit) ans += max(0ll, (pw-1)); 
				else ans += pw;
			}else ans += pw;
			st.in(s[j]);
			//if(i == n-1) cout << ans << '\n';
		}
		st.clear();
	}
	cout << ans;
	return;
}


int main() {
   
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    ll T;
    T=1;
   // cin >> T;
    //scanf("%lld",&T);
    ll CT = 0;
    //work();
    while(T--){
    	//cout << "Case " << ++CT <<": " ;
    	//printf("Case %lld: ",++CT);
		solve();
	}
    
    return 0;
}


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

int main(){
  int n;
  cin>>n;
  int a[10000];

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

  int mn = a[0], mx = a[0];
  long long sum = 0;
  for (int i=0;i<n;i++){
    mn = min(mn, a[i]);
    mx = max(mx, a[i]);
    sum += a[i];
  }

  cout<<mn<<" "<<mx<<" "<<sum<<endl;

  return 0;
}



Measured memory_bytes: 3124
n, m = map(int,input().split())
a = set()
for i in range(m):
    a.add(int(input()))
p = [0 for i in range(n+1)]
for i in range(1,n+1):
    if i in a:
        p[i] = 0
    elif i == 1:
        p[i] = 1
    elif i == 2:
        p[i] = p[1] + 1
    else:
        p[i] = p[i-1] + p[i-2]
print(p[n] % (10**9 + 7))

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

#define sz(x) (int) x.size()

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    string a;
    cin >> a;
    set<int> s[26];
    for (int i = 0; i < sz(a); i++) 
        a[i] -= 'a', s[a[i]].insert(i);
    int q;
    cin >> q;
    for (int t, l; q--;) {
        cin >> t >> l, l--;
        if (t == 1) {
            char c;
            cin >> c;
            s[a[l]].erase(l);
            a[l] = c - 'a';
            s[a[l]].insert(l);
        } else {
            int r, ans = 0;
            cin >> r;
            for (int i = 0; i < 26; i++) {
                auto x = s[i].lower_bound(l);
                ans += (x != s[i].end() && *x < r);
            }
            cout << ans << "\n";
        }
    }
    return 0;
}
    

Measured memory_bytes: 24220
import math, string, itertools, fractions, collections, re, array, bisect, sys, random, time, copy, functools
from heapq import heappush, heappop, heappushpop, heapify, heapreplace
input = sys.stdin.readline

N, M, S, T = [int(_) for _ in input().split()]
UVAB = [[int(_) for _ in input().split()] for _ in range(M)]
G1 = collections.defaultdict(lambda: collections.defaultdict(int))
G2 = collections.defaultdict(lambda: collections.defaultdict(int))

for u, v, a, b in UVAB:
    u -= 1
    v -= 1
    G1[u][v] = G1[v][u] = a
    G2[u][v] = G2[v][u] = b


def dijkstra(V, G, start):
    INF = float('inf')
    D = [INF for _ in range(V)]
    D[start] = 0
    H = [(0, start)]
    while H:
        du, u = heappop(H)
        if D[u] < du:
            continue
        for v, d in G[u].items():
            if D[v] > du + d:
                D[v] = du + d
                heappush(H, (D[v], v))
    return D


D1 = dijkstra(N, G1, S - 1)
D2 = dijkstra(N, G2, T - 1)

D = [10**15 - sum(_) for _ in zip(D1, D2)]
for i in range(N - 1, 0, -1):
    D[i - 1] = max(D[i - 1], D[i])
print(*D, sep='\n')


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

int main() {
    int N, x, f = 0;
    cin >> N;
    x = N;
    while (x != 0)
    {
        f += x % 10;
        x /= 10;
    }
    if (N % f == 0) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#define eps 1e-9

using namespace std;

int N, L;
double Dec[87000];

bool check(double x)
{
	double tank = L;
	for(int t = 0; t < 86400; t++){
		tank = min((double)L, tank - (Dec[t] - x));
		if(tank < eps) return false;
	}
	if(tank < eps) return false;
	
	double H = tank;
	for(int t = 0; t < 86400; t++){
		tank = min((double)L, tank - (Dec[t] - x));
		if(tank < eps) return false;
	}
	if(tank < eps) return false;
	
	if(H > tank) return false;
	
	return true;
}

int main(void)
{
	while(1){
		cin >> N >> L;
		if(N == 0 && L == 0) break;
		
		for(int i = 0; i < 86400; i++) Dec[i] = 0;
		int s, t; double u;
		for(int i = 1; i <= N; i++){
			cin >> s >> t >> u;
			for(int j = s; j < t; j++) Dec[j] = u;
		}
		
		double ub = 1000005, lb = 0, mid;
		for(int i = 0; i < 100; i++){
			mid = (ub + lb) * 0.5;
			if(check(mid)) ub = mid;
			else lb = mid;
		}
		printf("%.11f\n", (ub+lb)*0.5);
	}
	
	return 0;
}


Measured memory_bytes: 3760
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

const long MOD = 1000000007;
typedef pair<int, int> P;
typedef long long ll;

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

    int sum[N+1][N+1];
    for(int i=0; i<=N; i++){
        for(int j=0; j<=N; j++){
            sum[i][j] = 0;
        }
    }

    for(int i=2; i<=N; i++){
        int t = i;
        for(int j=2; j<=i; j++){
            if(t%j != 0) continue;
            int cnt = 0;
            while(t%j == 0){
                t /= j;
                cnt++;
            }
            sum[i][j] = cnt;
        }
    }

    for(int i=0; i<N; i++){
        for(int j=0; j<=N; j++){
            sum[i+1][j] += sum[i][j];
            // cout << i+1 << " " << j << " " << sum[i][j] << endl;
        }
    }

    int ans = 0;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            for(int k=j+1; k<=N; k++){
                if(i==j || j==k || i==k) continue;
                if(sum[N][i]>=2 && sum[N][j]>=4 && sum[N][k]>=4){
                    // cout << i << " " << j << " " << k << endl;
                    ans++;
                }
            }
        }
    }
    for(int i=1; i<=N; i++){
        if(sum[N][i]>=74) ans++;
        for(int j=1; j<=N; j++){
            if(i==j) continue;
            if(sum[N][i]>=14 && sum[N][j]>=4) ans++;
            if(sum[N][i]>=24 && sum[N][j]>=2) ans++;
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
typedef pair<int, int> pii;
/* constant */
const int INF = 1 << 30;
const ll LINF = 1LL << 50;
const int NIL = -1;
const int MAX = 10000;
const int mod = 1000000007;
const double pi = 3.141592653589;
/* global variables */
/* function */
/* main */
int main(){
    vector<int> cnt(13);
    int N; cin >> N;
    for (int i = 0; i < N; i++) {
        int a;
        cin >> a;
        cnt[a]++;
    }
    if (cnt[0] > 0) { cout << 0 << '\n'; return 0; }
    vector<int> base, search;
    base.push_back(0);
    base.push_back(24);
    for(int i = 1; i <= 12; i++) {
        if (cnt[i] >= 3) { cout << 0 << '\n'; return 0; }
        else if (cnt[i] == 1) search.push_back(i);
        else if (cnt[i] == 2) base.push_back(i), base.push_back(24 - i);
    }

    int size = search.size();
    int upper = 1 << size;
    int ans = 0;
    for (int b = 0; b < upper; b++) {
        vector<int> tmp(base.begin(), base.end());
        for (int i = 0; i < size; i++) {
            if ((b >> i) % 2) tmp.push_back(search[i]);
            else tmp.push_back(24 - search[i]);
        }
        int minD = 24;
        for (int i = 0; i < tmp.size()-1; i++) for (int j = i+1; j < tmp.size(); j++)
            minD = min(minD, abs(tmp[i] - tmp[j]));
        ans = max(ans, minD);
    }
    cout << ans << '\n';
}


Measured memory_bytes: 256
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	static int[][] map;
	static int[][] directions8= {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
	static int[][] directions4= {{-1,0},{1,0},{0,-1},{0,1}};
	static int ans;
	static int[] parent;//union-find用
	static int[] rank;//union-find用

	public static void main(String[] args) throws IOException {

		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		if(s.charAt(s.length()-1)=='s') {
			s = s+"e";
		}
		s+="s";


		System.out.println(s);
	}

	//素数判定
	public static boolean isPrime(long num) {
		if (num < 2) return false;
		else if (num == 2) return true;
		else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

		double sqrtNum = Math.sqrt(num);
		for (int i = 3; i <= sqrtNum; i += 2)
		{
			if (num % i == 0)
			{
				// 素数ではない
				return false;
			}
		}

		// 素数である
		return true;
	}

	//BFS用に二つの配列を足し算する
	static int[] addArrayElms(int[] a, int[] b) {
		int[] c = new int[a.length];
		for(int i = 0; i < a.length; i++) {
			c[i] = a[i] + b[i];
		}
		return c;
	}

	//	//二分探索
	//k <= num となる最小の配列要素kのインデックスを返す
	static private int binarySearch(long num, long[] orderedArray){
		int lowerBorder = -1;
		int upperBorder = orderedArray.length;
		int mid;

		while(upperBorder - lowerBorder >1) {
			mid = (upperBorder + lowerBorder)/2;
			if(orderedArray[mid]<=num) {
				lowerBorder = mid;
			}else {
				upperBorder = mid;
			}
		}
		return lowerBorder;
	}

	//二分探索
	//k <= num となる最小のList要素kのインデックスを返す
	static private int binarySearch(long num, ArrayList<Long> orderedList){
		int lowerBorder = -1;
		int upperBorder = orderedList.size();
		int mid;

		while(upperBorder - lowerBorder >1) {
			mid = (upperBorder + lowerBorder)/2;
			if(orderedList.get(mid)<=num) {
				lowerBorder = mid;
			}else {
				upperBorder = mid;
			}
		}
		return lowerBorder;
	}

	//aとbの最小公倍数を求める
	public static int gcd(int a, int b) {
		return b == 0 ? a: gcd(b, a % b);
	}
	public static long gcd(long a, long b) {
		return b == 0 ? a: gcd(b, a % b);
	}

	//Union-Find用の配列を要素数nで初期化
	static void ufInit(int n){
		parent = new int[n];
		rank = new int[n];
	}

	//Union-Findの要素の最上位の親（グループ名）を返す
	static int ufFind(int a) {
		if(parent[a]==a) {
			return a;
		}else {
			return ufFind(parent[a]);
		}
	}

	//Union-Find木を連結する
	static void ufUnite(int a, int b) {
		a = parent[a];
		b = parent[b];

		if(a==b) {
			return;
		}
		if(rank[a] > rank[b]){
			parent[b]=a;
		}else {
			parent[a]=b;
			if(rank[a]==rank[b]) {
				rank[b]++;
			}
		}
	}

	static boolean ufSame(int a, int b) {
		return ufFind(a)==ufFind(b);
	}
}


Measured memory_bytes: 38432
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

const int mod = 998244353;
struct mint {
  ll x;  // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint& operator+=(const mint a) {
    if((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if((x += mod - a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const { return mint(*this) += a; }
  mint operator-(const mint a) const { return mint(*this) -= a; }
  mint operator*(const mint a) const { return mint(*this) *= a; }
  mint pow(ll t) const {
    if(!t) return 1;
    mint a = pow(t >> 1);
    a *= a;
    if(t & 1) a *= *this;
    return a;
  }
  // for prime mod
  mint inv() const { return pow(mod - 2); }
  mint& operator/=(const mint a) { return *this *= a.inv(); }
  mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x; }
ostream& operator<<(ostream& os, const mint& a) { return os << a.x; }
mint fact(int n) {
  if(n == 1 || n == 0) return 1;
  mint res = n;
  return res * fact(n - 1);
}

struct combination {
  vector<mint> fact, ifact;
  combination(int n) : fact(n + 1), ifact(n + 1) {
    assert(n < mod);
    fact[0] = 1;
    for(int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
    ifact[n] = fact[n].inv();
    for(int i = n; i >= 1; --i) ifact[i - 1] = ifact[i] * i;
  }
  mint operator()(int n, int k) {
    if(k < 0 || k > n) return 0;
    return fact[n] * ifact[k] * ifact[n - k];
  }
};

int main() {
  ll n, m, k;
  cin >> n >> m >> k;
  combination c(1e6);
  mint ans = 0;
  rep(i, k + 1) {
    mint now = c(n - 1, i) * mint(m - 1).pow(n - 1 - i) * m;
    ans += now;
  }
  cout << ans << endl;
}

Measured memory_bytes: 18788
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Linq;
using static MyIO;


public class D
{
	public static void Main() => (new Solver()).Solve();
}


public class Solver
{
	public void Solve()
	{
		int N = GetInt();
		long[] A = GetLongs(N);

		long[] csum = new long[N + 1];
		for(int i = 0; i < N; i++)
			csum[i + 1] = csum[i] + A[i];

		long ans = long.MaxValue / 2;
		for(int i = 2; i < N - 1; i++)
		{
			int leftSpl = meguruBinarySearch(csum, 1, i);
			int rightSpl = meguruBinarySearch(csum, i + 1, N);
			for(int j = 0; j < 2; j++)
			{
				if(leftSpl - j < 0)
					continue;

				for(int k = 0; k < 2; k++)
				{
					if(rightSpl - k < i)
						continue;
					
					long P = csum[leftSpl - j];
					long Q = csum[i] - csum[leftSpl - j];			
					long R = csum[rightSpl - k] - csum[i];
					long S = csum[N] - csum[rightSpl - k];
					
					long max = Math.Max(P, Math.Max(Q, Math.Max(R, S)));
					long min = Math.Min(P, Math.Min(Q, Math.Min(R, S)));
					ans = Math.Min(ans, max - min);
				}				
			}
		}

		Console.WriteLine(ans);
	}

	private int meguruBinarySearch(long[] csum, int first, int last)
	{
		long sum = csum[last] - csum[first - 1];
		int ok = last;
		int ng = first - 1;
		while(Math.Abs(ng - ok) > 1)
		{
			int mid = (ng + ok) / 2;
			if((csum[mid] - csum[first - 1]) * 2 > sum)
				ok = mid;
			else
				ng = mid;
		}
		return ok;
	}
}


public static class MyIO
{
	private static string[] args = null;
	private static int num = -1;
	private static int used = -1;

	private static string getArg()
	{
		if(used == num)
		{
			args = Console.ReadLine().Split(' ');
			num = args.Length;
			used = 0;
		}
		return args[used++];
	}

	public static int GetInt() => int.Parse(getArg());
	public static long GetLong() => long.Parse(getArg());
	public static double GetDouble() => double.Parse(getArg());
	public static string GetString() => getArg();
	public static char GetChar() => getArg()[0];
	public static int[] GetInts(int N) => Enumerable.Range(0, N).Select(_ => GetInt()).ToArray();
	public static long[] GetLongs(int N) => Enumerable.Range(0, N).Select(_ => GetLong()).ToArray();
	public static double[] GetDoubles(int N) => Enumerable.Range(0, N).Select(_ => GetDouble()).ToArray();
	public static string[] GetStrings(int N) => Enumerable.Range(0, N).Select(_ => GetString()).ToArray();
}


Measured memory_bytes: 35676
#include <iostream>

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)n; ++i)

int main(void){
	while(true){
		int sum;
		cin >> sum;
		if(sum == 0) return 0;
		rep(i, 9){
			int x;
			cin >> x;
			sum -= x;
		}
		cout << sum << endl;
	}
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
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 SZ(i) int(i.size())
#ifdef tmd
#define IOS()
#define debug(...) fprintf(stderr,"%s - %d (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define debug(...)
#endif

const int MAXN = 1000006;
const ll MOD = 1000000007;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll ans = 1000;

ll cnt;
bool qry (ll x) {
    cnt++;
    assert(cnt <= 64);
    assert(x >= 1 && x <= 1000000000000000000LL);
    cout << "? " << x << endl;
    #ifdef tmd
    string sa = to_string(ans);
    string sx = to_string(x);
    return (x <= ans && sx <= sa) || (x > ans && sx > sa);
    #else
    char res;
    cin >> res;
    return res == 'Y';
    #endif
}
/*********************GoodLuck***********************/
int main () {
    IOS();

#ifdef tmd
    cin >> ans;
#endif // tmd

    ll bs = 1;
    ll dg = 0;

    ll tt = INF;
    ll ft = -1;
    REP (i, 12) {
        bs *= 10;
        bool q1 = qry(bs), q2 = qry(bs-1);
        debug(q1, q2);
        if (!q1 && q2) {
            dg = i;
            ft = bs;
            break;
        } else if (q1 && q2) {
            tt = min(tt, bs);
        }
    }

    debug(tt, ft);

    if (tt < INF && ft == -1) {
        cout << "! " << tt / 10 << endl;
        return 0;
    } else if (tt == ft / 10) {
        cout << "! " << ft - 1 << endl;
        return 0;
    }
    ll cur = 0;
    REP (i, dg) {
        ll l = 0, r = 10;
        while (l < r - 1) {
            ll m = (l + r) >> 1;
            if (qry(cur * 10 + m)) {
                l = m;
            } else {
                r = m;
            }
        }
        cur = cur * 10 + l;
    }

    ll l = -1, r = 10;
    while (l < r - 1) {
        ll m = (l + r) >> 1;
        if (qry(cur * 100 + m*10 + 9)) {
            r = m;
        } else {
            l = m;
        }
    }
    cur = cur * 10 + r;


    debug(cur);

    cout << "! " << cur << endl;
    return 0;
}


Measured memory_bytes: 596
#include <stdio.h>
#include <string.h>

int get_sum(int num, int sum, int *u, int n){
	int i, j;
    
    if (num == 0 && sum == 0){
        return (1);
	}
    
    if (n > 9){
        return (0);
    }
    
    return (get_sum(num - 1, sum - u[n], u, n + 1) + get_sum(num, sum, u, n + 1));
}

int main(void)
{
	int sum, num;
    int u[10];
    int i;
	
	while (1){
		scanf("%d%d", &num, &sum);
		if (num == 0 && sum == 0) break;
		
        for (i = 0; i < 10; i++){
            u[i] = i;
        }
        
		printf("%d\n", get_sum(num, sum, u, 0));
	}
	
	return (0);
}

Measured memory_bytes: 0