akhauriyash/Code-Regression huggingface dataset:
/**
 *      ///----- My Info -----///
 *      Code by: Ernesto Abreu
 *      Codeforces User: Ernest0_0Abreu
 *      Country: Cuba
 *      E-mail: ernestoabreup@gmail.com
 *      CopyRight
**/
#include <bits/stdc++.h>
#ifdef Ernest0_0Abreu
#include <debug/to_string.h>
#endif
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
    	///----- My Template -----///
///======================================================================================================================================
/// Red-Black Tree
// #include <ext/pb_ds/assoc_container.hpp>  // .find_of_order(x); .order_of_key(x);
// using namespace __gnu_pbds;
// typedef tree< int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update > indexed_set;
/// Function
#define pi (acos(-1))
#define lg2(x) 31-__builtin_clz(x)
#define lgx(x,b) log(b)/log(x)
/// Macros
#define fst first
#define scd second
#define left (node<<1)
#define right ((node<<1)+1)
#define size(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
/// Debug
#define _end cout << "\n"
#ifdef Ernest0_0Abreu
#define db(x) cerr << "[ "<< #x << " ]: " << to_string(x) << "\n"
#define dbrange(x,begin,end) cerr << "[ "<< #x << " ]: " << to_string(x,begin,end) << "\n"
#define dbname(x) cerr << to_string(x,#x) << "\n"
#define dbnamerange(x,begin,end) cerr << to_string(x,#x,begin,end) << "\n"
#define dbmat(x,begin_n,end_n,begin_m,end_m) cerr << to_string(x,#x,begin_n,end_n,begin_m,end_m) << "\n"
#else 
#define db(x) ;
#define dbrange(x,begin,end) ;
#define dbname(x) ;
#define dbnamerange(x,begin,end) ;
#define dbmat(x,begin_n,end_n,begin_m,end_m) ;
#endif
/// Typedef
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
/// Constant
const int MAXN = 1e6+7;
const int MOD = 1e9+7;
const ull BASE = 311;
const ld EPS = 1e-9;
const int INF = ((1<<30)-1);
const ll INFLL = ((1ll<<62ll)-1ll);
const ll oo = 2e18;
/// Hash Prime Numbers: 2, 277, 293, 307, 331, 337, 1009, 2027;
/// Module Prime Numbers: 3, 998244353, 1000000007, 1000000009, 1000000021, 1000000033;
///=======================================================================================================================================
#define int long long
		///----- My code -----///



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

	int a, b, c, d;
	cin >> a >> b >> c >> d;
	int i = -1;
	while(a > 0 && c > 0){
		i++;
		if(i&1) a -= d;
		else c -= b;
	}
	if(a <= 0) cout << "No";
	else cout << "Yes";
	
	return 0;
}

Measured memory_bytes: 3668
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); i++)
int main(){
    int n, y; cin >> n >> y;
    int a, b, c;
    y /= 1000;
    for (a=0; a<=n;a++){
        for(b=0; b<=n;b++){
                /*if ((10 * a) + (5*b)+ (n-a-b) < y || b<0||c<0){
                    cout << -1 << " " << -1 << " " << -1 << endl;
                    return 0;
                }*/
          if (n-a-b < 0){
                    b=n+1;
            continue;
                }
                if ((10 * a) + (5*b)+ n-a-b == y){
                    cout << a << " " << b << " " << n-a-b << endl;
                    return 0;
                }
                /*`else if (y + 5 > (10 * a) + (5*b)+n-a-b && (10 * a) + (5*b)+c >= y + 1){
                    b--; c++;
                    continue;
                }
                else if (y + 9 > (10 * a) + (5*b)+n-a-b && (10 * a) + (5*b)+c >= y + 5){
                    a--; b++;
                    continue;
                }
                else if ((10 * a) + (5*b)+ n-a-b >= y + 9){
                    a--; c++;
                    continue;
                }*/
        }
    }
    cout << -1 << " " << -1 << " " << -1 << endl;
    return 0;
}

Measured memory_bytes: 3600
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<vector>
#define inf 2147483647
#define rep(i,a,b) for(int i=a;i<b;i++)
#define  rr read()
#define ll long long
#define repb(i,a,b) for(int i=a;i<=b;i++)
#define CloseIo   ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;
int read()
{
    char ch = getchar();
	int x = 0, f = 1;
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while('0' <= ch && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
const int N=1005;
char a[1005][1005];
	int n,m,ans=0;
int vis[N][N];
struct node
{
	 int x,y,c;
	 node(int ssx,int ssy,int sc)
	 {
	 	 x=ssx;
	 	 y=ssy;
	 	 c=sc;
	 }
};
 queue<node>q;
 int sx[]={1,0,-1,0};
 int sy[]={0,-1,0,1};
void bfs()
{
	
	while(!q.empty())
	{
		node t=q.front();
		 q.pop();
		 for(int i=0;i<4;i++)
		 {
		 	 int xx=t.x+sx[i],yy=t.y+sy[i];
		 	 if(xx>=0&&xx<n&&yy>=0&&yy<m&&!vis[xx][yy])
		 	 {
		 	 	q.push(node(xx,yy,t.c+1));
		 	 	vis[xx][yy]=1;
		 	 	ans=max(ans,t.c+1);
			  }
		 }
	}
}
int main()
{

 scanf("%d %d",&n,&m);
 getchar();
   rep(i,0,n)
   {
   	  rep(j,0,m)
   {scanf("%c",&a[i][j]);
   if(a[i][j]=='#')
   {vis[i][j]=1;
   q.push(node(i,j,0));
   }
   }
   getchar();
   }
   bfs();
cout<<ans;
}




Measured memory_bytes: 17296
// Let's bring the sky down :)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 5;
ll a[N], b[N], c[N];
ll dp[N][2][2][2];
int maxx(int x, int  y, int z){
    return(max(x, max(y, z)));
}
int main()
{
    ios_base ::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i] >> b[i] >> c[i];
    }
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < 2; j++){
            for(int k = 0; k < 2; k++){
                for(int l = 0; l < 2; l++){
                    int sum = j + k + l;
                    if(sum != 1) continue;
                    if(j)
                        dp[i][j][k][l] = a[i] + maxx(dp[i - 1][0][0][0],
                                             dp[i - 1][0][1][0],
                                             dp[i - 1][0][0][1]);
                    else if(k)
                        dp[i][j][k][l] = b[i] + maxx(dp[i - 1][1][0][0],
                                             dp[i - 1][0][0][0],
                                             dp[i - 1][0][0][1]);
                    else if(l)
                        dp[i][j][k][l] = c[i] + maxx(dp[i - 1][1][0][0],
                                             dp[i - 1][0][1][0],
                                             dp[i - 1][0][0][0]);
                }
            }
        }
    }
    cout << maxx(dp[n][0][0][1],
                 dp[n][0][1][0],
                 dp[n][1][0][0]);
return 0;
}


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

using namespace std;
typedef pair <long, long> pii;

int vacation[3][1000000];

pii mayorYelimina(int dia){
    int maxi = 0;
    int toElimin;
    for(int i = 0; i < 3; ++i){
        if(vacation[i][dia] > maxi) toElimin = i;
        maxi = max(maxi, vacation[i][dia]);
    }
    vacation[toElimin][dia] = 0;
    return {maxi, toElimin};
}

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

    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif // ONLINE_JUDGE


    int n; cin>>n;
    vector <int> dp(3);
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < 3; ++j){
            cin>>vacation[j][i];
        }
        vector <int> ndp(3);
        for(int j = 0; j < 3; ++j){
            for(int k = 0; k < 3; ++k){
                if(j == k) continue;
                ndp[j] = max(ndp[j], dp[k] + vacation[k][i]);
            }
        }
        dp = ndp;
    }

    cout<<max(max(dp[0], dp[1]), dp[2])<<endl;
    return 0;
}


Measured memory_bytes: 8832
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define Rep(i, a, b) for(int i = a; i <= b; i++)
#define _GLIBCXX_DEBUG
#define Vl vector<ll>
#define Vs vector<string>
#define Vp vector<pair<ll, ll>>
#define ll long long
#define ALL(v) (v).begin(),(v).end()
using namespace std;
const double pi = acos(-1.0);
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;

// 最大公約数
ll gcd(ll a, ll b)
{
   if (a%b == 0) {
       return(b);
   } else {
       return(gcd(b, a%b));
   }
}

// 最小公倍数
ll lcm(ll a, ll b){
   return a / gcd(a, b) * b;
}

//素数判定
bool is_prime(const unsigned n){
    switch(n){
        case 0: // fall-through
        case 1: return false;
        case 2: // fall-through
        case 3: return true;
    } // n > 3 が保証された
    if(n % 2 == 0 || n % 3 == 0) return false;
    for(unsigned i = 5; i * i <= n; i += 6) {
        if(n % i     == 0) return false; // (6の倍数)-1
        if(n % (i+2) == 0) return false; // (6の倍数)+1
    }
    return true;
}

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

/*   *   *   *   *   *   *   *   *   *   *   */

void solve() {
    vector<vector<ll>> c(3,vector<ll>(3));
    rep(i, 0, 3) rep(j, 0, 3) cin >> c[i][j];
    bool f = true;
    rep(i, 0, 2){
        if(c[i][0]-c[i+1][0]!=c[i][1]-c[i+1][1]
        || c[i][1]-c[i+1][1]!=c[i][2]-c[i+1][2]
        || c[i][2]-c[i+1][2]!=c[i][0]-c[i+1][0]) f = false;
    }
    if(f) cout << "Yes" << endl;
    else cout << "No" << endl;
}

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

    solve();
    return 0;
}


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

def chk(a,t):
  ans=0
  x=0
  for i in a:
    x+=i
    if t==True and x<1:
      ans+=1-x
      x=1
    elif t==False and x>-1:
      ans+=x+1
      x=-1
    t = not t
  return ans
  
print(min(chk(a,True),chk(a,False)))

Measured memory_bytes: 14332
#include <stdio.h>
#include <string>
#include <iostream>
using namespace std;

int main()
{
	int i, w,b;
	string S;
	cin >> S;
	cin >> w;
	b = S.size() / w;
	if (S.size() % w == 0) {
		b = b - 1;
	}
	for (i = 0; i < b+1; i++) {
		cout << S[w*i] << "";
	}
	
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner scan = new java.util.Scanner(System.in);
        double x1 = scan.nextDouble();
        double y1 = scan.nextDouble();
        double x2 = scan.nextDouble();
        double y2 = scan.nextDouble();
        double dx = x2 - x1;
        double dy = y2 - y1;
        double d = Math.sqrt(dx * dx + dy * dy);
        System.out.println(d);
    }
}

Measured memory_bytes: 27928
import math
N=int(input())
W=list(map(int,input().split()))
H=sum(W)/2
X=0
for i in range(N) :
    X+= W[i]
    if X >= H :
        ans1=int(math.sqrt((sum(W[:i])-sum(W[i:]))**2))
        ans2=int(math.sqrt((sum(W[:i+1])-sum(W[i+1:]))**2))
        break
if ans1 < ans2 :
    print(ans1)
else:
    print(ans2)

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

static int H, W;

bool inside(int r, int c) {
    return 0 <= r and r < H and 0 <= c and c < W;
}

int main() {
    cin >> H >> W;

    vector<string> S(H);
    for (int i = 0; i < H; i++) {
        cin >> S[i];
    }

    for (int r = 0; r < H; r++) {
        for (int c = 0; c < W; c++) {
            if (S[r][c] == '#') continue;

            int cnt = 0;
            for (int dr = -1; dr <= 1; dr++) {
                for (int dc = -1; dc <= 1; dc++) {
                    if (dr == 0 and dc == 0) continue;
                    int nr = r + dr,
                        nc = c + dc;
                    if (inside(nr, nc) and S[nr][nc] == '#') cnt++;
                }
            }
            S[r][c] = char('0' + cnt);
        }
    }

    for (int r = 0; r < H; r++) {
        cout << S[r] << endl;
    }

    return 0;
}

Measured memory_bytes: 256
//include
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

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

//change
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return true;
    }
    return false;
}

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

template <class T>
inline T nCr(T n, T r)
{
    T num = 1;
    for (int i = 1; i <= r; ++i)
    {
        num *= (n - i + 1) / i;
    }
    return num;
}
template <class T>
inline T nPr(T n, T r)
{
    r = n - r;
    T sum = 1;
    int i;
    for (i = n; i >= r + 1; --i)
        sum *= i;
    return sum;
}

template <class T>
inline T facctorial(T k)
{
    T sum = 1;
    for (int i = 1; i <= k; ++i)
    {
        sum *= i;
    }
    return sum;
}

//numeric
template <class T>
inline T gcd(T a, T b)
{
    if (a < b)
    {
        a ^= b;
        b ^= a;
        a ^= b;
    }

    return b ? gcd(b, a % b) : a;
}

template <class T>
inline T lcm(T a, T b)
{
    return a * b / gcd(a, b);
}

//typedef
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SZ(a) int((a).size())
#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())

//repetition
#define FOR(i, a, b) for (int i = (a); i <= (int)(b); ++i)
#define REP(i, n) FOR(i, 0, n)

//constant
constexpr double EPS = 1e-10;
const double PI = acos(-1.0);
constexpr LL INF = 1e10;

//clear memory
#define CLR(a) memset((a), 0, sizeof(a))

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

int main()
{
    int n, k, q;
    cin >> n >> k >> q;
    vector<int> a(q);
    vector<int> point(n, k);
    for (int i = 0; i < q; ++i)
    {
        cin >> a[i];
        ++point[a[i] - 1];
    }
    for (int i = 0; i < n; ++i)
    {
        point[i] -= q;
        if (point[i] > 0)
        {
            cout << "Yes\n";
        }
        else
        {
            cout << "No\n";
        }
    }
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> vvl;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvec;
typedef vector<vector<bool>> vveb;
typedef vector<vector<string>> vves;
#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 rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pb push_back
#define pp pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
typedef long long int64;
//const int64 INF = 1LL << 58;
#define dame { puts("-1"); return 0;}
#define YES { cout << "YES" << endl; return 0; }
#define NO { cout << "NO" << endl; return 0; }
#define Yes { cout << "Yes" << endl; return 0; }
#define No { cout << "No" << endl; return 0; }
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 (a>b) { a=b; return 1; } return 0; }
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};


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

    int a,b;
    cin >> a >> b;
    if(a%2==1 && b%2 == 1) Yes
    No
    return 0;
}
    

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll,ll> P;
typedef string str;
typedef vector<P> vp;
typedef vector<string> vs;
typedef vector<bool> vb;

const ll mod=1e9+7;
const ll inf=1e16;

#define rep(i,m,n) for(ll i=m;i<n;i++)
#define repr(i,m,n) for(ll i=m-1;i>=n;i--)
#define fi first
#define se second
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
#define eb(x) emplace_back(x)
#define pb(x) pop_back(x)
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define sum(x) accumulate(all(x),0)
#define pc(x) __builtin_popcount(x)
#define gll greater<ll>()

void solve(){
  ll n;
  cin >>n;

  cout << (n-2)*180 << endl;
}

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


Measured memory_bytes: 3564
//PDF解説に倣って深さ優先探索
#include<bits/stdc++.h>
using namespace std;
int n,var;
vector<vector<int>> a,b,day;
vector<vector<bool>> seen;
bool possible=true;

void dfs(int p1, int p2){
  if (!possible || day[p1][p2]!=0) return; //閉路あり or 調査済み
  if (seen[p1][p2]){ //閉路検出(前提:day[p1][p2]==0)
    possible=false;
    return;
  }
  
  seen[p1][p2]=true;
  int b1=b[p1][p2], b2=b[p2][p1];
  if (b1==n-2 && b2==n-2){ //両選手とも最終試合
    day[p1][p2]=1;
    return;
  }
  int np1,np2;
  if (b1<n-2){
    var=a[p1][b1+1]; np1=min(p1,var); np2=max(p1,var);
    dfs(np1,np2);
    day[p1][p2]=max(day[p1][p2],day[np1][np2]);
  }
  if (b2<n-2){
    var=a[p2][b2+1]; np1=min(p2,var); np2=max(p2,var);
    dfs(np1,np2);
    day[p1][p2]=max(day[p1][p2],day[np1][np2]);
  }
  day[p1][p2]++;
  return;
}

int main(){
  cin>> n;
  a.assign(n,vector<int>(n-1));
  b.assign(n,vector<int>(n));
  day.assign(n,vector<int>(n));
  seen.assign(n,vector<bool>(n));
  /*  a[i][j]:選手iがj番目にあたる選手
      b[i][j]:選手iが選手jとあたる順番
    day[i][j]:選手iと選手jの試合の、最終試合から数えた最小の日数*/
  for (int i=0; i<n; i++){
    for (int j=0; j<n-1; j++){
      cin>> var;
      a[i][j]=var-1;
      b[i][var-1]=j;
    }
  }
  
  for (int i=0; i<n; i++){
    dfs(i,a[i][0]);
  }
  
  int ans=-1;
  if (possible){
    for (int i=0; i<n; i++){
      ans=max(ans,day[i][a[i][0]]);
    }
  }
  
  cout<< ans <<endl;
}
//自力の解法は1日一試合だと O(n^3) になったと思われる

Measured memory_bytes: 12416
import sys
sys.setrecursionlimit(100000000)


def main():
    solve()


def solve():
    for data in get_dataset():
        print search(data)


def search(data):
    count = 0
    H = len(data)
    W = len(data[0])
    for i in xrange(H):
        for j in xrange(W):
            if data[i][j] == '.':
                continue
            _search(i, j, H, W, data[i][j], data)
            count += 1
    return count


def _search(i, j, H, W, cell, data):
    data[i][j] = '.'
    for a in xrange(i-1, i+2):
        if not -1 < a < H:
            continue
        for b in xrange(j-1, j+2):
            if not -1 < b < W:
                continue

            if a != i and b != j:
                continue

            if data[a][b] == '.':
                continue

            if cell == data[a][b]:
                _search(a, b, H, W, cell, data)
    return


def get_dataset():
    dataset = []
    while True:
        line = raw_input().rstrip().split()
        H = int(line[0])
        if H == 0:
            break

        data = []
        for i in xrange(H):
            data.append(list(raw_input().rstrip()))
        dataset.append(data)
    return dataset


if __name__ == '__main__':
    main()

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

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

  if(a == b){
    for(int i = 0; i < b - 1; i++){
      cout << a;
    }
    cout << a << endl;
  }

  else{
    for(int i = 0; i < max(a , b) - 1; i++){
      cout << min(a , b);
    }
    cout << min(a , b) << endl;
  }

}


Measured memory_bytes: 256
use proconio::fastout;
use whiteread::parse_line;

#[fastout]
fn main() {
    let n: usize = parse_line().unwrap();
    let mut s: Vec<char> = parse_line::<String>().unwrap().chars().collect();

    let mut left = 0;
    let mut right = n - 1;
    let mut ret = 0;
    loop {
        while left < n && s[left] != 'W' {
            left += 1;
        }
        while s[right] != 'R' {
            if right == 0 {
                break;
            }
            right -= 1;
        }
        if left >= n || (right == 0 && s[0] == 'W') || right < left {
            break;
        }
        s[left] = 'R';
        s[right] = 'W';
        ret += 1;
    }
    println!("{}", ret);
}


Measured memory_bytes: 3116
// created by mtnshh
 
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
 
#define ll long long
#define ld long double
 
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repb(i,a,b) for(ll i=a;i>=b;i--)
 
#define err() cout<<"=================================="<<endl;
#define errA(A) for(auto i:A)   cout<<i<<" ";cout<<endl;
#define err1(a) cout<<#a<<" "<<a<<endl
#define err2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<endl
#define err3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<endl
#define err4(a,b,c,d) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<" "<<#d<<" "<<d<<endl
 
#define pb push_back
#define all(A)  A.begin(),A.end()
#define allr(A)    A.rbegin(),A.rend()
#define ft first
#define sd second
 
#define pll pair<ll,ll>
#define V vector<ll>
#define S set<ll>
#define VV vector<V>
#define Vpll vector<pll>
 
#define endl "\n"
 
const ll logN = 20;
const ll M = 1000000007;
const ll INF = 1e12;
#define PI 3.14159265
 
const ll N = 100005;

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	ll w,h,k;
	cin>>h>>w>>k;
	char A[h][w];
	rep(i,0,h)	rep(j,0,w)	cin>>A[i][j];
	ll ans = M;
	rep(mask,0,(1<<(h-1))){
		V v;
		ll cnt=0;
		v.pb(0);
		rep(i,0,h-1){
			if(mask&(1<<i))	cnt++, v.pb(0);	
		}
		bool f1=1;
		rep(i,0,w){
			bool f=0;
			ll l=0;
			rep(j,0,h){
				if(A[j][i]=='1')
					v[l]++;
				if(j!=(h-1) and (mask&(1<<j)))
					l++;	
			}
			ll ma=0;
			for(auto i:v)
				ma=max(ma,i);
			if(ma>k){
				if(f1){
					cnt = M;
					break;
				}
				else{
					f1 = 0;
					cnt++;
					for(auto &i:v){
						i = 0;	
					}
					ll l=0;
					rep(j,0,h){
						if(A[j][i]=='1')
							v[l]++;
						if(j!=h-1 and (mask&(1<<j)))
							l++;		
					}
				}
			}
			else
				f1 = 0;
		}
		ll ma=0;
		for(auto i:v)
			ma=max(ma,i);
		if(ma > k)
			cnt = M;
		ans = min(ans, cnt);
	}
	cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
# -*- coding:utf8 -*-

n, l = map(int, input().split())
t = [l + i - 1 for i in range(1, n+1)]
if 0 in t:
    ans = sum(t)
elif -1 >= t[-1]:
    ans = sum(t[:-1])
else:
    ans = sum(t[1:])
print(ans)



Measured memory_bytes: 3060
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#define inf 0x7ffffff7
#define MAXN  100010
#define PII pair<int, int>
#define e 2.718281828459
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
ll dis[MAXN] = { 0 };
vector<pair<ll, ll>> v[MAXN];
void dfs(ll x, ll fa)
{
	for (int i = 0; i < v[x].size(); i++)
	{
		if (v[x][i].first == fa)
			continue;
		dis[v[x][i].first] = dis[x] + v[x][i].second;
		dfs(v[x][i].first, x);
	}
}
int main()
{
	int n, x, y;
	ll d;
	cin >> n;
	for (int i = 1; i < n; i++)
	{
		cin >> x >> y >> d;
		v[x].push_back(pair<ll, ll>(y, d));
		v[y].push_back(pair<ll, ll>(x, d));
	}
	ll q, k;
	cin >> q >> k;
	dfs(k, -1);
	while (q--)
	{
		cin >> x >> y;
		cout << dis[x] + dis[y] << endl;
	}
	//cin >> T;
	return 0;
}


Measured memory_bytes: 14336
import java.util.Scanner;

public class Main {
	public static void main (String[] args) {
//------------------------------------------------------------

		Scanner sc =new Scanner(System.in);
		String s = sc.nextLine();
		sc.close();

		for (int i = 0 ; i<s.length(); i+=2) {
			System.out.print(s.charAt(i));
		}
//------------------------------------------------------------
	}
}

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

#define rep(i,N) for(int i=0;i<N;i++)
#define rep2(i,N) for(int i=1;i<=N;i++)
using namespace std;
long long  INF=1e18;
long long mod=1e9+7;

//status unsolved

int main(){
    long long n,k;
    cin>>n>>k;

    vector<long long >a(n+1);

    rep2(i,n)cin>>a[i];

    bool reached[n+1]={};
    int now=1;
    vector<int>route;
    long long res=0;
    long long size=0;
    while(1){
    if(reached[now]){
        int n=route.size();
        rep(i,route.size()){
            if(route[i]==now){
            res=i;
            break;
            }
        }
        break;
    }
    reached[now]=true;
    route.emplace_back(now);
    now=a[now];
    size++;
    }
    
    //res:=ループに入るまでのワープ回数
    if(k<res){
        cout<<route[k]<<endl;
        return 0;
    }
    else{
    //cout<<res<<endl;
    k-=res;
    long long loop=size-res;
    k%=loop;
    //cout<<k<<endl;
    cout<<route[k+res]<<endl;
    return 0;
    }
    return 0;

}
/*


*/


Measured memory_bytes: 6076
#![allow(unused_imports)]
#![allow(unused_macros)]
use std::cmp::{max, min};
use std::collections::*;
use std::io::{stdin, Read};

trait ChMinMax {
    fn chmin(&mut self, other: Self);
    fn chmax(&mut self, other: Self);
}
impl<T> ChMinMax for T
where
    T: PartialOrd,
{
    fn chmin(&mut self, other: Self) {
        if *self > other {
            *self = other
        }
    }
    fn chmax(&mut self, other: Self) {
        if *self < other {
            *self = other
        }
    }
}

#[allow(unused_macros)]
macro_rules! parse {
    ($it: ident ) => {};
    ($it: ident, ) => {};
    ($it: ident, $var:ident : $t:tt $($r:tt)*) => {
        let $var = parse_val!($it, $t);
        parse!($it $($r)*);
    };
    ($it: ident, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = parse_val!($it, $t);
        parse!($it $($r)*);
    };
    ($it: ident, $var:ident $($r:tt)*) => {
        let $var = parse_val!($it, usize);
        parse!($it $($r)*);
    };
}

#[allow(unused_macros)]
macro_rules! parse_val {
    ($it: ident, [$t:tt; $len:expr]) => {
        (0..$len).map(|_| parse_val!($it, $t)).collect::<Vec<_>>();
    };
    ($it: ident, ($($t: tt),*)) => {
        ($(parse_val!($it, $t)),*)
    };
    ($it: ident, u1) => {
        $it.next().unwrap().parse::<usize>().unwrap() -1
    };
    ($it: ident, $t: ty) => {
        $it.next().unwrap().parse::<$t>().unwrap()
    };
}

#[cfg(debug_assertions)]
macro_rules! debug {
    ($( $args:expr ),*) => { eprintln!( $( $args ),* ); }
}

#[cfg(not(debug_assertions))]
macro_rules! debug {
    ($( $args:expr ),*) => {
        ()
    };
}

fn solve(s: &str) {
    let mut it = s.split_whitespace();
    let n = it.next().unwrap().chars().map(|x| x.to_digit(10).unwrap());
    let mut ret = 0;
    for ni in n {
        ret += ni;
        ret %= 9;
    }
    if ret == 0 {
        println!("{}", "Yes");
    } else {
        println!("{}", "No");
    }
}

fn main() {
    let mut s = String::new();
    stdin().read_to_string(&mut s).unwrap();
    solve(&s);
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_input() {
        let s = "
        ";
        solve(s);
    }
}


Measured memory_bytes: 2196
import qualified Data.ByteString.Char8         as BC
import           Data.Maybe                     ( fromJust )
import           Control.Applicative

readInts :: IO [Int]
readInts = map (fst . fromJust . BC.readInt) . BC.words <$> BC.getLine

check :: [Int] -> String
check [a, b, c] | a < b && b < c = "Yes"
                | otherwise      = "No"
main :: IO ()
main = readInts >>= putStrLn <$> check



Measured memory_bytes: 3508
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
//問題文および制約はちゃんと確認しよう！
//サイズは10^5じゃなくて2×10^5とかかもしれないし、重要な制約・条件を見落としているかも
//とりあえずサンプルを読んでから解法を考えよう？
string s;int K,n;
lint dp[110][5][2];
int main()
{
	cin>>s;cin>>K;
	n=s.size();
	//reverse(All(s));
	memset(dp,false,sizeof(dp));
	dp[0][0][0]=1;
	rep(i,n) rep(j,K+1){
		//cout<<i<<' '<<j<<' '<<dp[i][j][0]<<' '<<dp[i][j][1]<<endl;
		rep(k,10){
			int nj=j;if(k>0) nj++;
			if(k<(s[i]-'0')){
				//cout<<'a'<<endl;
				dp[i+1][nj][1]+=dp[i][j][0]+dp[i][j][1];
			}
			else if(k>(s[i]-'0')){
				dp[i+1][nj][1]+=dp[i][j][1];
			}
			else{
				dp[i+1][nj][1]+=dp[i][j][1];
				dp[i+1][nj][0]+=dp[i][j][0];
			}
		}
	}
	lint out=dp[n][K][0]+dp[n][K][1];
	cout<<out<<endl;
}


Measured memory_bytes: 256
//Leonidas
//#pragma GCC optimize("Ofast")
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container'.',hpp>
//#include <ext/pb_ds/tree_policy'.',hpp>
//typedef tree < int , null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> TREE;
#define ll long long
#define ull unsigned long long int
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define pii pair<int,int>
#define pss pair<short,short>
#define pld pair<long double,long double >
#define ld long double
#define piii  pair<pii,int>
#define vii vector<pair<int,int> >
#define st first
#define nd second
#define pll pair<ll,ll>
#define speed ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define M_PI 3.14159265358979323846
//#define int long long
const int mod=1000000007;
//const int mod=1009;
//const int mod=998244353;
const int inf=1000000009;
const long long INF=1000000000000000009;
const long long big=1000000000000000;
const long double eps=0.000000000000000000001;
using namespace std;
int W[505][505],B[505][505];
int n;
pii K[4]={mp(1,0),mp(-1,0),mp(0,1),mp(0,-1)};
pii operator+ (pii a,pii b)
{
    return mp(a.st+b.st,a.nd+b.nd);
}
pii get(int x)
{
    int r=x%n;
    if(r==0)
        r=n;
    return mp((x-1)/n+1,r);
}
bool good(pii x)
{
    if(x.st>=1&&x.st<=n&&x.nd>=1&&x.nd<=n)
        return 1;
    return 0;
}
void propagate(pii x)
{
    if(!good(x))
        return;
    for(int i=0;i<4;i++)
    {
        pii v=x+K[i];
        if(W[v.st][v.nd]>W[x.st][x.nd]+B[x.st][x.nd])
        {
            W[v.st][v.nd]=W[x.st][x.nd]+B[x.st][x.nd];
            propagate(v);
        }
    }
}
int32_t main()
{
    speed
    cin>>n;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            W[i][j]=min(i-1,min(j-1,min(n-i,n-j))),B[i][j]=1;
    ll wynik=0;
    for(int i=1; i<=n*n; i++)
    {
        int l;
        cin>>l;
        pii x=get(l);
        wynik+=W[x.st][x.nd];
        B[x.st][x.nd]=0;
        propagate(x);
       // cout<<i<<" "<<wynik<<endl;
    }
    cout<<wynik;

    return 0;
}


Measured memory_bytes: 20788
#include <bits/stdc++.h>
#define show(x) cerr << #x << " = " << x << endl
using namespace std;
using ld = long double;
int main()
{
    auto out = [](const ld y, const ld x, const ld sp) {
        const ld PI = 3.141592653589793;
        const ld F = 0.22451398828979266;
        const ld r1 = sqrt(sp / F / 5);
        const ld r2 = r1 * F / 0.5877852522924731;
        const ld theta = 0.1 * PI;
        for (int i = 0; i < 10; i++) {
            const ld s = theta * i * 2;
            const ld r = i % 2 == 0 ? r1 : r2;
            cout << fixed << setprecision(15) << x + r * cos(s) << " " << y + r * sin(s) << endl;
        }
    };
    int N;
    cin >> N;
    vector<ld> S(N);
    for (int i = 0; i < N; i++) { cin >> S[i]; }
    for (int i = 0; i < N; i++) {
        const ld y = (2 * (i / 10) + 1) * 500 - 5000;
        const ld x = (2 * (i % 10) + 1) * 500 - 5000;
        cout << i + 1 << endl;
        out(y, x, (i == 0 ? 1.5 * S[i] : (S[i] + S[i - 1]) * 0.5));
    }
    return 0;
}



Measured memory_bytes: 3592
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define mod 1000000007
#define PI 3.1415926535897932384626433
#define se second
#define fi first
#define pb push_back
#define T true
#define F false
#define endl "\n"
typedef char ch;
typedef bool boll;
typedef string st;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef set < string > sst;
typedef set < long long > sl;
typedef queue < long long > que;
typedef vector < long long > vec;
typedef map < long long, long long > mll;
typedef pair < long long, long long > pll;
typedef vector < pair < long long, long long > > vpl;
typedef pair < long long, unsigned long long > pul;

int main()
{
    fast;
    int a;
    cin >> a;
    string ans="No";
    while(a){
        if(a%10==7){
            ans="Yes";
            break;
        }
        else a = a/10;
    }
    cout << ans;

}

Measured memory_bytes: 3636
N,M,Q = map(int,input().split())
data = [list(map(int,input().split())) for i in range(Q)]

from itertools import combinations_with_replacement

A = [int(i) for i in range(1,M+1)]

ans = 0
for i in list(combinations_with_replacement(A,N)):
    p = 0
    for j in range(Q):
        if i[data[j][1]-1]-i[data[j][0]-1] == data[j][2]:
            p += data[j][3]
    ans = max(ans,p)

print(ans)

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

class Dice{
public: 
    int n[6];
    const int N[4] = {0, 1, 5, 4};
    const int S[4] = {0, 4, 5, 1};
    const int E[4] = {0, 3, 5, 2};
    const int W[4] = {0, 2, 5, 3};
    
    void roll(char dir);
};

void Dice::roll(char dir){
    const int *r_dir;
    int temp;
    
    if(dir == 'N') r_dir = N;
    else if(dir == 'S') r_dir = S;
    else if(dir == 'E') r_dir = E;
    else r_dir = W;
    
    temp = n[r_dir[0]];
    for(int i = 0; i < 4; i++){
        if(i == 3) n[r_dir[i]] = temp;
        else n[r_dir[i]] = n[r_dir[i + 1]];
    }
}

int main(){
    Dice dice;
    string str;
    
    for(int i = 0; i < 6; i++){
        cin >> dice.n[i];
    }
    
    cin >> str;
    for(int i = 0; i < str.size(); i++){
        dice.roll(str[i]);
    }
    
    cout << dice.n[0] << endl;
}


Measured memory_bytes: 3188
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0197

"""
import sys
from sys import stdin
input = stdin.readline


def solve(a, b):
    count = 0
    if a > b:
        X, Y = a, b
    else:
        X, Y = b, a

    r  = 1
    while r:
        r = X % Y
        X = r
        X, Y = Y, X
        count += 1
    return X, count


def main(args):
    while True:
        a, b = map(int, input().split())
        if a == 0 and b == 0:
            break
        gcd, count = solve(a, b)
        print(gcd, count)


if __name__ == '__main__':
    main(sys.argv[1:])

Measured memory_bytes: 7928
#include <iostream>
using namespace std;
int main()
{
	int a, b, c, d, cnt = 1;
	cin >> a >> b >> c >> d;
	while (a > 0 && c > 0)
	{
		if (cnt % 2)
		{
			c -= b;
		}
		else
		{
			a -= d;
		}
		cnt++;
	}
	if (a > 0)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 3632
#include<iostream>


#include<queue>
#include<algorithm>
#include<vector>
#include<string>
#include<utility>
#include<cstdlib>
#include<math.h>
using namespace std;

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




int main() {
	int a, b;
	cin >> a >> b;
	if ((a + b) % 2 == 0)cout << (a + b) / 2 << endl;
	else cout << "IMPOSSIBLE" << endl;
	return 0;
}


Measured memory_bytes: 256
import math
 
serach_number = 10 ** 5 + 4

def sieve_of_eratosthenes(target):
    dest = int(math.sqrt(target))
    target_list = list(range(2, target + 1))
    prime_list = []
 
    while True:
        num_min = min(target_list)
        if num_min >= dest:
            prime_list.extend(target_list)
            break
        prime_list.append(num_min)
 
 
        i = 0
 
        while True:
            if i >= len(target_list):
                break
            elif target_list[i] % num_min == 0:
                target_list.pop(i)
            i += 1
 
    return prime_list
 
ps = sieve_of_eratosthenes(serach_number)

x = int(input())

while x < 10 ** 5 + 4:
  if x in ps:
    print(x)
    break
  else:
    x += 1


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

const int MAX_N = 110000;
int memo[MAX_N];

int rec(int n){
    if (n==0) return 0;
    if (memo[n] != -1) return memo[n];

    int res = n;

    for (int pow6=1;pow6<=n;pow6*=6) res = min(res, rec(n-pow6)+1);
    for (int pow9=1;pow9<=n;pow9*=9) res = min(res, rec(n-pow9)+1);

    return memo[n] = res;
}
int main() {
    int N; cin >> N;

    for (int i=0;i<MAX_N; ++i) memo[i] = -1;
    cout << rec(N) << endl;
    return 0;
}

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

int main(){
    int a[5]; for(int i=0;i<5;i++) cin >> a[i];
    int hasuu=1e9;
    int sum=0;
    for(int i=0;i<5;i++){
        if(a[i]%10!=0) hasuu=min(hasuu,a[i]%10);
        sum+=(a[i]+9)/10*10;
    }
    if(hasuu==1e9) hasuu=10;
    cout << sum+hasuu-10 << endl;
}

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

int main() {

string s, t;
int n=0;

	cin >> s;
	for(int i = 0; i < s.size(); i++){
         s[i] = tolower(s[i]);
    }

	while(cin >> t) {
        if(t=="END_OF_TEXT"){
            break;
        }

		for(int i = 0; i < t.size(); i++){
             t[i] = tolower(t[i]);
        }

		if(s == t){
             n++;
        }

	}
	cout<<n<<endl;
	return 0;
}



Measured memory_bytes: 3216
// AOJ Volume 1 Problem 0160 Delivery Fee


#include <stdio.h>

int main(void)
{
    int n;
    int x, y, h, w;
    int size;
    int fee;
    int total_fee;
    int i;

    while (1){
        scanf("%d", &n);
        if (n == 0){
            break;
        }
        
        total_fee = 0;
        
        for (i = 0; i < n; i++){
            scanf("%d%d%d%d", &x, &y, &h, &w);
            size = x + y + h;
            
            fee = -1;
            if (size <= 60){
                fee = 600;
            }
            else if (size <= 80){
                fee = 800;
            }
            else if (size <= 100){
                fee = 1000;
            }
            else if (size <= 120){
                fee = 1200;
            }
            else if (size <= 140){
                fee = 1400;
            }
            else if (size <= 160){
                fee = 1600;
            }
            
            if (fee != -1){
                if (w <= 2){
                    if (fee < 600) fee = 600;
                }
                else if (w <= 5){
                    if (fee < 800) fee = 800;
                }
                else if (w <= 10){
                    if (fee < 1000) fee = 1000;
                }
                else if (w <= 15){
                    if (fee < 1200) fee = 1200;
                }
                else if (w <= 20){
                    if (fee < 1400) fee = 1400;
                }
                else if (w <= 25){
                    if (fee < 1600) fee = 1600;
                }
                else {
                    fee = -1;
                }
            }
                
            if (fee != -1){
                total_fee += fee;
            }
        }

        printf("%d\n", total_fee);
    }
    
    return (0);
}

Measured memory_bytes: 0
import sys
def input(): return sys.stdin.readline().strip()
mod = 998244353

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=998244353):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

comb = Combination(2 * 10 ** 5)

def main():
    N, M, K = map(int, input().split())

    if K == 0:
        ans = pow(M - 1, N - 1, mod) * M
        print(ans % mod)
        return

    ans = 0
    for i in range(K + 1):
        val = comb(N - 1, i) * M * pow(M - 1, N - i - 1, mod)
        val %= mod
        ans += val
        ans %= mod
    print(ans)



if __name__ == "__main__":
    main()


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

int main(){
  int h, w;
  char t[52][52];
  int dp[52][52];

  while(cin >> h >> w){
    for(int i = 0; i < h; i++){
      cin >> t[i];
      for(int j = 0; j < w; j++){
        t[i][j] -= '0';
      }
    }

    dp[0][0] = t[0][0];
    for(int i = 0; i < h; i++){
      for(int j = 0; j < w; j++){
        if(i == 0 && j == 0) continue;
        int tmp = INT_MAX;
        if(0 <= i - 1) tmp = min(tmp, dp[i - 1][j] + (int)t[i][j]);
        if(0 <= j - 1) tmp = min(tmp, dp[i][j - 1] + (int)t[i][j]);
        dp[i][j] = tmp;
      }
    }

    cout << (int)dp[h - 1][w - 1] << endl;
  }
}

Measured memory_bytes: 1176
#[allow(dead_code)]
fn is_whitespace(c: &char) -> bool {
    c.is_whitespace()
}

#[allow(dead_code)]
fn is_eol(c: &char) -> bool {
    ['\r', '\n'].contains(c)
}

#[allow(unused_macros)]
macro_rules! input {
    ($var:ident, $($r:tt)*) => {
        input_inner!{$var, $($r)*}
    };

    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        #[allow(unused_mut, unused_variables, bare_trait_objects)]
        let mut next = move |f: &Fn(&char)->bool| -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|f(&c))
                .take_while(|c|!f(&c))
                .collect()
        };
        input_inner!{next, $($r)*};
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

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

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

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; eol ]) => {
        $next(&is_eol).split(' ').map(|x| x.parse::<$t>().unwrap()).collect::<Vec<_>>()
    };

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

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

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

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

    ($next:expr, parser) => {
        $next
    };

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

#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::{BinaryHeap, HashMap};

#[allow(dead_code)]
type Graph = Vec<Vec<usize>>;
#[allow(dead_code)]
const M: usize = 1e9 as usize + 9;

fn main() {
    input! {
        n: usize,
        m: usize,
        res: [(usize1, chars); m],
    }
    let mut solved = vec![false; n];
    let mut penas = vec![0; n];
    let mut solves = 0;
    let mut penacnt = 0;
    for i in 0..m {
        if res[i].1[0] == 'A' {
            if !solved[res[i].0] {
                solves += 1;
                penacnt += penas[res[i].0];
                solved[res[i].0] = true;
            }
        } else {
            if !solved[res[i].0] {
                penas[res[i].0] += 1;
            }
        }
    }

    println!("{} {}", solves, penacnt);
}


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

using namespace std;

int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int n;
    scanf("%d", &n);
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
        --a[i];
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        int b = a[i];
        if (a[b] == i)
            ++ans;
    }
    cout << ans / 2 << endl;
    return 0;
}


Measured memory_bytes: 640
#define DEB
#include<bits/stdc++.h>
#define REP(i,m) for(int i=0;i<(m);++i)
#define REPN(i,m,in) for(int i=(in);i<(m);++i)
#define ALL(t) (t).begin(),(t).end()
#define CLR(a) memset((a),0,sizeof(a))
#define pb push_back
#define mp make_pair
#define fr first
#define sc second

using namespace std;


#ifdef DEB
#define dump(x)  cerr << #x << " = " << (x) << endl
#define prl cerr<<"called:"<< __LINE__<<endl
#define dumpR(x) cerr<<"\x1b[31m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpY(x) cerr<<"\x1b[33m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpG(x) cerr<<"\x1b[32m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
#else
#define dump(x) ;
#define dumpR(x) ;
#define dumpY(x) ;
#define dumpG(x) ;
#define prl ;
template<class T> void debug(T a,T b){ ;}
#endif

template<class T> void chmin(T& a,const T& b) { if(a>b) a=b; }
template<class T> void chmax(T& a,const T& b) { if(a<b) a=b; }

typedef long long int lint;
typedef pair<int,int> pi;

namespace std{
  template<class S,class T>
  ostream &operator <<(ostream& out,const pair<S,T>& a){
    out<<'('<<a.fr<<','<<a.sc<<')';
    return out;
  }
}

//const int INF=5e8;
char s[500005],sr[500005];
int n;
int table[500005],rev[500005];

void KMP(char* s,int* table){
  int klen=strlen(s);
  table[0]=0;
  REPN(i,klen+1,1){
    int j=table[i-1];
    while(j>0 && s[j]!=s[i]) j=table[j-1];
    if(s[j]==s[i]) ++j;
    table[i]=j;
  }
}
int main(){
  scanf("%s",s);
  n=strlen(s);
  REP(i,n) sr[n-1-i]=s[i];
  KMP(s,table);
  KMP(sr,rev);

  int block=n-table[n-1];
  if(n%block==0 && block<n){
    int K=n/block;
    if(block==1){
      printf("%d %d\n",n,1);
    }else{
      int res=0;
      for(int i=1;i<n;++i){
        int j=n-i;
        if((i%(i-table[i-1])==0 && i>(i-table[i-1])) || ((j%(j-rev[j-1])==0 && j>(j-rev[j-1])))) ;
        else ++res;
      }
      printf("%d %d\n",2,res);
    }
  }else{
    printf("%d %d\n",1,1);
  }


  return 0;
}





Measured memory_bytes: 5120
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
int main() {
	int k;
	int s;
	cin >> k >> s;

	int x;
	int y;
	int z;

	int count;
	count = 0;
	for (x = 0; x <= k; x++) {
		for (y = 0; y <= k; y++) {
			if ((s - x - y <= k) && (s - x - y >= 0)) count++;
		}
	}

	cout << count << endl;

	return 0;
}

Measured memory_bytes: 3660