akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

#define boost ios::sync_with_stdio(); cin.tie(); cout.tie();
#define ll long long
#define ld long double
#define pii pair <int, int>
#define pll pair <ll, ll>
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define vt vector 
#define all(c) (c).begin(), (c).end()
#define sz(x) (int)(x).size()

template<class T> bool umin(T& a, const T& b) {
	return b<a?a=b, 1:0;
}
template<class T> bool umax(T& a, const T& b) { 
	return a<b?a=b, 1:0;
} 

const int INF = 1e9 + 10;
const int mod = 1e9 + 7;
const ll LLINF = 1e18 + 10;

void solve() 
{
	string s;
	cin >> s;
	int ans =0;
	for(int i=0;i < s.size();i++){
		if(s[i] == 'R'){
			int curr = 1;
			for(int j = i+1; j < s.size(); j++){
				if(s[j] == 'R'){
					curr++;
				}
				else{
					break;
				}
			}
			umax(ans,curr);
		}
	}
	cout << ans;
}
int main()
{
    boost
    //int t; read(t); while(t--)
    solve();
}


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

int main(){
  int a=0;
 string s;
  cin>>s;
  if(s.at(0)!='A'){
    cout << "WA" <<endl;
    return 0;
  }
  if(s.at(1)<'a'){
      cout << "WA" <<endl;
    return 0;
  } 
  for(int i=2;i<s.size()-1;i++){
   	  if(s.at(i)<'a' && s.at(i)!='C'){
        cout << "WA" <<endl;
        break;
   	  }
       else if(s.at(i)=='C' && a==0){
        a = 1;
      }
       else if(s.at(i)=='C' && a==1){
        cout << "WA" <<endl;
        return 0;
       }
    }
    if(a == 0){
      cout << "WA" <<endl;
      return 0;
    }
  if(s.at(s.size()-1)<'a'){
      cout << "WA" <<endl;
    return 0;
  }
  cout << "AC" << endl;
}

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

int main(){
	int n,x,y;
	cin >> n >> x >> y;
	--x,--y;
	int dp[n][n];
	memset(dp,0,sizeof(dp));
	for(int i =0;i<n;i++){
		dp[i][i] = 0;
		if(i!=n-1)
			dp[i][i+1] = 1;
	}
	for(int i =0;i<n-1;i++){
		for(int j = i+1;j<n;j++){
			dp[i][j] = dp[i][j-1] + 1;
		}
	}

	dp[x][y] = 1;
	for(int i =x+1;i<y;i++){
		dp[x][i] = min(dp[x][i],dp[i][y]+1);
		dp[i][y] = min(dp[i][y],1+dp[x][i]);
	}

	for(int i =0;i<n-1;i++){
		for(int j = i+1;j<n;j++){
			dp[i][j] = min(dp[i][j],min(dp[min(i,x)][max(i,x)]+dp[min(x,j)][max(j,x)],dp[min(i,y)][max(i,y)] + dp[min(y,j)][max(y,j)]));
		}
	}
	int ans[n];
	memset(ans,0,sizeof(ans));
	for(int i =0;i<n;i++){
		for(int j =i+1;j<n;j++){
			ans[dp[i][j]-1]++;
		}
	}

	for(int i =0;i<n-1;i++){
		cout << ans[i] << endl;
	}

}

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

typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pl;

const int INT_INF = 2147483646;
const ll LL_INF = 9223372036854775807;
const double PI=3.1415926535897932;

bool SecondCompare(const pair<int,int> &a,const pair<int,int> &b)
{
       return a.second<b.second;
}
 
bool SecondCompareDes(const pair<int,int> &a,const pair<int,int> &b)
{
       return a.second>b.second;
}

ll minll(ll a, ll b){
    if(a >= b)  return b;
    else    return a;
}

ll maxll(ll a, ll b){
    if(a >= b)  return a;
    else    return b;
}

ll gcd(ll a, ll b){
    ll tmp;
    if(a%b == 0){
        return b;
    }
    else{
        return gcd(b, a%b);
    }
}

ll mod = 1e9+7;
ll inv(ll x) {
    ll res = 1;
    ll k = mod - 2;
    ll y = x;
    while (k) {
        if (k & 1) res = (res * y) % mod;
        y = (y * y) % mod;
        k /= 2;
    }
    return res;
}

const ll SIZE = 1e6+10;
ll x,y;
ll ama = 1e9+7;
ll fact[SIZE], fact_inv[SIZE];

ll mod_pow(ll x, ll n){
    if(n == 0) return 1;
    ll res = mod_pow(x * x % ama, n / 2);
    if(n & 1) res = res * x % ama;
    return res;
}
ll combination(ll n, ll k){
    return (((fact[n] * fact_inv[k]) % ama )* fact_inv[n - k]) % ama;
}


 ll h,w,n;

int main(){

    cin >> h >> w >> n;
    ll ma = max(h,w);
    ll ans = n/ma;
    if(n%ma != 0)   ++ans;
    cout << ans << endl;

}

Measured memory_bytes: 256
h, w = map(int, input().split())
ans = 10000000000
for i in range(1, h):
  a = i * w
  b = ((h - i) // 2) * w
  c = h * w - a - b
  if ans > (max(a, c) - min(a, b)):
    ans = max(a, c) - min(a, b)
  
  b = (h - i) * (w // 2)
  c = h * w - a - b
  if ans > (max(a, c) - min(a, b)):
    ans = max(a, c) - min(a, b)

for i in range(1, w):
  a = i * h
  b = ((w - i) // 2) * h
  c = h * w - a - b
  if ans > (max(a, c) - min(a, b)):
    ans = max(a, c) - min(a, b)
  
  b = (w - i) * (h // 2)
  c = h * w - a - b
  if ans > (max(a, c) - min(a, b)):
    ans = max(a, c) - min(a, b)
print(ans)

Measured memory_bytes: 3188
import java.util.*;
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String ans = "No";
    int[][] A = new int[3][3];
    for(int i = 0;i < 3;i++){
      for(int j = 0;j < 3;j++){
        A[i][j] = sc.nextInt();
      }
    }
    int N = sc.nextInt();
    for(int j = 0;j < N;j++){
      int b = sc.nextInt();
      for(int i = 0;i < 3;i++){
        for(int k = 0;k < 3;k++){
          if(b == A[i][k]){
            A[i][k] = 0;
          }
        }
      }
    }

    for(int i = 0;i < 3;i++){
      if(A[i][0] == A[i][1] && A[i][0] == A[i][2]){
        ans = "Yes";
      }else if(A[0][i] == A[1][i] && A[1][i] == A[2][i]){
        ans = "Yes";
      }
    }
    if(A[0][0] == A[1][1] && A[1][1] == A[2][2]){
      ans = "Yes";
    }else if(A[0][2] == A[1][1] && A[1][1] == A[2][0]){
      ans = "Yes";
    }
    System.out.print(ans);
  }
}

Measured memory_bytes: 21844
#include <cstdio>
#include <cstdlib>

using namespace std;

class inverse {
    public:
    inverse(int n, int mod);
    ~inverse();
    long long get_inv(int x);
    long long get_fact(int x);
    long long get_invfact(int x);
    long long get_comb(int x, int y);
    
    private:
    int mod;
    long long* inv;
    long long* fact;
    long long* invfact;
};

inverse::inverse(int n, int mod) : mod(mod) {
    inv = (long long *)malloc(sizeof(long long) * (n + 1));
    fact = (long long *)malloc(sizeof(long long) * (n + 1));
    invfact = (long long *)malloc(sizeof(long long) * (n + 1));
    inv[1] = 1;
    for (int i = 2; i <= n; i++) inv[i] = inv[mod % i] * (mod - mod / i) % mod;
    fact[0] = invfact[0] = 1;
    for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % mod;
    for (int i = 1; i <= n; i++) invfact[i] = invfact[i - 1] * inv[i] % mod;
}

inverse::~inverse() {
    free(inv);
    free(fact);
    free(invfact);
}

long long inverse::get_inv(int x) {
    return inv[x];
}

long long inverse::get_fact(int x) {
    return fact[x];
}

long long inverse::get_invfact(int x) {
    return invfact[x];
}

long long inverse::get_comb(int x, int y) {
    return fact[x] * invfact[y] % mod * invfact[x - y] % mod;
}

int main() {
    int m = 998244353, i;
    long long n, a, b, k, ans = 0;
    
    scanf("%lld %lld %lld %lld", &n, &a, &b, &k);
    
    inverse inv(n, m);
    
    for (i = 0; i <= n && a * i <= k; i++) {
        long long x = k - a * i;
        
        if (x % b == 0 && x / b <= n) {
            ans += inv.get_comb(n, i) * inv.get_comb(n, x / b) % m;
            if (ans >= m) ans -= m;
        }
    }
    
    printf("%lld\n", ans);
    
    return 0;
}


Measured memory_bytes: 7296
/**
 *    author:  FromDihPout
 *    created: 2020-06-19
**/

#include <bits/stdc++.h>
using namespace std;

template<typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first + r.first, l.second + r.second); }
template<typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first - r.first, l.second - r.second); }
#define f first
#define s second

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    long long h, w, n;
    cin >> h >> w >> n;
    set<pair<int,int>> black, seen;
    for (int i = 0; i < n; i++) {
        pair<int,int> pos;
        cin >> pos.f >> pos.s;
        black.insert(pos);
    }
    
    vector<pair<int,int>> start = { {-2,-2}, {-2,-1}, {-2,0},
                                    {-1,-2}, {-1,-1}, {-1,0},
                                    {0,-2}, {0,-1}, {0,0} };
    vector<long long> cnt(10);
    cnt[0] = (h - 2) * (w - 2);
    for (auto b : black) {
        for (int i = 0; i < 9; i++) {
            pair<int,int> pos = b + start[i];
            if (pos.f < 1 || pos.s < 1) {
                continue;
            }
            else if (pos.f + 2 > h || pos.s + 2 > w) {
                continue;
            }
            else if (seen.count(pos)) {
                continue;
            }
            seen.insert(pos);
            int black_squares = 0;
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < 3; k++) {
                    if (black.count({pos.f + j, pos.s + k})) {
                        black_squares++;
                    }
                }
            }
            cnt[black_squares]++;
            cnt[0]--;
        }
    }
    
    for (int i = 0; i < 10; i++) {
        cout << cnt[i] << '\n';
    }
    return 0;
}

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

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

void YN(bool flg){if(flg) cout << "YES" << endl; else cout << "NO" << endl;}
void Yn(bool flg){if(flg) cout << "Yes" << endl; else cout << "No" << endl;}
void yn(bool flg){if(flg) cout << "yes" << endl; else cout << "no" << endl;}

bool ship[2][200100];

int main() {
    int n, m;
    cin >> n >> m;
    rep(i, m) {
        int from, to;
        cin >> from >> to;
        from--, to--;
        if(from == 0) ship[0][to] = true;
        if(to == n-1) ship[1][from] = true;
    }

    bool can = false;
    rep(i, n) {
        if(ship[0][i] && ship[1][i]) can = true;
    }

    if(can) cout << "POSSIBLE" << endl;
    else cout << "IMPOSSIBLE" << endl;

    return 0;
}


Measured memory_bytes: 640
def main():
    n=int(input())
    a=list(map(int,input().split()))
    cnt=0
    for i in range(n):
        if (i+1)%2==0: continue
        if a[i]%2==0: continue
        cnt+=1
    print(cnt)
    return

if __name__=='__main__':
    main()


Measured memory_bytes: 9188
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define NUM 1000000007
#define MAX 100001
#define INF LLONG_MAX
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n,k,tmp;
    cin>>n>>k;
    vector<ll> v;
    for(int i=0;i<n;i++){
        cin>>tmp;
        v.pb(tmp);
    }
    vector<ll> dp(n+1,INT_MAX);
    dp[n-1]=0;
    for(int i=n-2;i>=0;i--){
        for(int j=i+1;j<=min(i+k,n-1);j++){
            ll mini = abs(v[i]-v[j]);
            dp[i]=min(dp[i],mini+dp[j]);
        }
    }
    cout<<dp[0]<<endl;
    return 0;
}


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

using namespace std;
using ll =long long;
typedef pair<int,int> P;
#define SORT(a) sort((a).begin(),(a).end())
#define REV(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cerr << #x << " = " << (x) << endl;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

void coY() {cout <<"Yes"<<endl;}
void coN(){cout <<"No"<<endl;}
 
//Write From this Line

//const ll mod = 1e9+7;
//const ll mod = 998244353;
int main()
{
	int n, m;
	cin >> n >> m;

	vector<vector<int>> s(n);
	rep(i,m){
		int k;
		cin >> k;
		rep(j,k){
			int x;
			cin >> x;
			--x;
			// x を押すと i が反応
			s[x].push_back(i);
		}
	}
	vector<int> p(m);
	rep(i,m) cin >> p[i];

	int ans = 0;
	for(int tmp = 0; tmp < (1 << n); tmp++){
		bitset<10> bit(tmp);
		vector<int> kazu(m,0);

		rep(i,n){
			if(bit.test(i)){
				// スイッチ i を使う
				for(auto x:s[i]){
					kazu[x] = 1 - kazu[x];
				}
			}
		}

		bool f = true;
		rep(i,m){
			if(p[i] != kazu[i]) f=  false;
		}
		if(f) ans++;
	}
	cout << ans << endl;
}


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

int main(){
    int a, b, c;
    while(scanf("%d %d %d", &a, &b, &c)!=EOF){
        if(a>=-100&&a<=100 && b>=-100&&b<=100 && c>=-100&&c<=100){
            if(c>=a && c<=b){
                printf("Yes\n");
            }else{
                printf("No\n");
            }
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#define MAXL 3005
using namespace std;

int dp[MAXL][MAXL];
int from[MAXL][MAXL][2];
char s[MAXL], t[MAXL];
int s_len, t_len;

void solve() {
    int i, j;
    for (i = 1; s[i]; ++i) {
        for (j = 1; t[j]; ++j) {
            if (s[i] == t[j]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                from[i][j][0] = i - 1, from[i][j][1] = j - 1;
            } else {
                if (dp[i][j - 1] > dp[i - 1][j]) {
                    dp[i][j] = dp[i][j - 1];
                    from[i][j][0] = i, from[i][j][1] = j - 1;
                } else {
                    dp[i][j] = dp[i - 1][j];
                    from[i][j][0] = i - 1, from[i][j][1] = j;
                }
            }
        }
    }
    s_len = i, t_len = j;
}

void print(int x, int y) {
    if ((!x) || (!y)) return;
    print(from[x][y][0], from[x][y][1]);
    if (s[x] == t[y]) putchar(s[x]);
}

int main() {
    scanf("%s%s", s + 1, t + 1);
    solve();
    print(s_len - 1, t_len - 1);
    return 0;
}

Measured memory_bytes: 105984
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int dfs(int i,vector<int>* v,int* vis){
    vis[i]=1;
    int ans=1;
    for(int j=0;j<v[i].size();j++){
        if(!vis[v[i][j]]){
            ans+=dfs(v[i][j],v,vis);
        }
    }
    return ans;
}
int main() {
	int n,m;
	cin>>n>>m;
	int vis[n+1];
	vector<int> v[n+1];
	for(int i=0;i<=n;i++){
	    vis[i]=0;
	}
	for(int i=0;i<m;i++){
	    int s,f;
	    cin>>s>>f;
	    v[s].push_back(f);
	    v[f].push_back(s);
	}
	int ans=0;
	for(int i=1;i<=n;i++){
	    if(!vis[i]){
	        int count=dfs(i,v,vis);
	        if(count>ans)
	        ans=count;
	    }
	}
	cout<<ans;
	return 0;
}


Measured memory_bytes: 24636
#include <memory.h>
#include <stdio.h>

#define arr_print_card(a, n) for(int i=0;i<(n);++i)printf(i==(n)-1?"%c%d\n":"%c%d ",(a)[i].symbol, (a)[i].num)

typedef struct Card {
    char symbol;
    int num;

    bool operator<(const Card &right) const {
        return num < right.num;
    }

    bool operator!=(const Card &right) const {
        return symbol != right.symbol || num != right.num;
    }
} Card;

void bubble_sort(Card *a, const int N) {
    for(int i = 0; i < N; ++i) {
        for(int j = N - 1; j > i; --j) {
            if(a[j] < a[j - 1]) {
                Card tmp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = tmp;
            }
        }
    }
}

void selection_sort(Card *a, const int N) {
    for(int i = 0; i < N; ++i) {
        int minj = i;
        for(int j = i + 1; j < N; ++j) {
            if(a[j] < a[minj]) minj = j;
        }
        if(i != minj) {
            Card tmp = a[i];
            a[i] = a[minj];
            a[minj] = tmp;
        }
    }
}

bool arr_cmp(Card *a, Card *b, const int N) {
    for(int i = 0; i < N; ++i) {
        if(a[i] != b[i]) return false;
    }
    return true;
}

int main() {
    int n;
    scanf("%d\n", &n);
    Card a[n], b[n];
    for(int i = 0; i < n; ++i) {
        scanf(" %c%d", &a[i].symbol, &a[i].num);
    }
    memcpy(b, a, sizeof(b));
    bubble_sort(a, n);
    selection_sort(b, n);

    arr_print_card(a, n);
    printf("Stable\n");
    arr_print_card(b, n);
    printf(arr_cmp(a,b,n)?"Stable\n":"Not stable\n");
    return 0;
}



Measured memory_bytes: 2672
#include<iostream>
#include<algorithm>
using namespace std;
bool notfound(int arr[],int x,int n){
   int i=0,j=n-1;
   while(i<=j){
   	int mid = (i+j)/2;
   	if(arr[mid]==x){
   		return false;
   	}
   	else if(arr[mid]<x){
   		i = mid+1;
   	}else if(arr[mid]>x){
   		j = mid - 1;
   	}
   }
   return true;
}
int main(){
	int x,n;
	cin >> x >> n;
	if(n<=0){
		cout<<x<<endl;
		return 0;
	}

	int arr[n];
	for(int i =0;i<n;i++){
		cin>>arr[i];
	}
	//if(n==1){
	//	if(abs(x-arr[0])>=1){
		//	cout<<x<<endl;
	//		return 0;
	//	}
	//}
	sort(arr,arr+n);
	int i=1;
	if(notfound(arr,x,n)){  //&&abs((x-i)-x)>0
			cout<<x<<endl;
            return 0;
		}
	while(true){
		if(notfound(arr,x-i,n)){  //&&abs((x-i)-x)>0
			cout<<x-i<<endl;
			return 0;
		}
		 if(notfound(arr,x+i,n)){  //&&abs((x-i)-x)>0
			cout<<x+i<<endl;
            return 0;
		}
		i++;
	}
}

Measured memory_bytes: 3636
import collections
n = int(raw_input())
s = raw_input()

def f(k, s):	
	if k == 0:
		return True
 	cc = collections.Counter()
	q = collections.deque()
	for j in range(k - 1, len(s)):
		q.append(s[j - k + 1:j+1])
		if len(q) == k + 1:
			u = q.popleft()
			cc[u] += 1
		if s[j- k+1:j+1] in cc:
			return True	
	return False
lo,hi = 0, n
while(lo < hi):
	med = (lo + hi + 1) / 2
	if f(med, s):
		lo = med
	else:
		hi = med - 1

print lo

Measured memory_bytes: 107932
import collections, sys
sys.setrecursionlimit(100005)
N = int(input())
A = [int(_) for _ in input().split()]
INF = float('inf')
memo = collections.defaultdict(lambda: INF)


def c(start, res):
    if memo[start, res] != INF:
        return memo[start, res]
    elif 2 * res - 1 > N - start:
        memo[start, res] = -INF
    elif start >= N:
        memo[start, res] = -INF
    elif res > 1:
        memo[start, res] = max(A[start] + c(start + 2, res - 1),
                               c(start + 1, res), c(start + 2, res))
    else:
        memo[start, res] = max(A[start], c(start + 1, res))
    return memo[start, res]


print(c(0, N // 2))


Measured memory_bytes: 151548
#include <algorithm>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
// const int INF = (1 << 30) - 1;
// const ll LL_INF = (1LL << 62) - 1;
// const ll MOD = 1e9 + 7;

int N;
vector<int> P, Q;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> N;
  P.resize(N);
  for (int i = 0; i < N; i++) {
    int pi;
    cin >> pi;
    P[i] = pi;
  }
  Q.resize(N);
  for (int i = 0; i < N; i++) {
    int qi;
    cin >> qi;
    Q[i] = qi;
  }

  vector<int> s_P = P;
  sort(s_P.begin(), s_P.end());
  vector<int> s_Q = Q;
  sort(s_Q.begin(), s_Q.end());

  int a = 0;
  do {
    a++;
    bool f = true;
    for (int i = 0; i < P.size(); i++) {
      if (P[i] != s_P[i]) {
        f = false;
        break;
      }
    }
    if (f) {
      break;
    }
  } while (next_permutation(s_P.begin(), s_P.end()));

  int b = 0;
  do {
    b++;
    bool f = true;
    for (int i = 0; i < Q.size(); i++) {
      if (Q[i] != s_Q[i]) {
        f = false;
        break;
      }
    }
    if (f) {
      break;
    }
  } while (next_permutation(s_Q.begin(), s_Q.end()));

  int ans = abs(a - b);
  cout << ans << endl;
  return 0;
}

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

int main(){
  int h, w; cin >> h >> w;
  vector<string> s(h);
  for(int i = 0; i < h; i++) cin >> s[i];
  /*vector<vector<char>> a(h, vector<char> (w));
  for(int i = 0; i < h; i++){
  for(int j = 0; j < w; j++){
  	a[i][j] = s[i][j];
  }
  }*/
  
  vector<vector<int>> l(h, vector<int> (w)), r(h, vector<int> (w)), u(h, vector<int> (w)), d(h, vector<int> (w));
  for(int i = 0; i < h; i++){
  for(int j = 0; j < w; j++){
  	if(s[i][j] == '#') l[i][j] = 0;
    
    else if(j == 0) l[i][j] = 1;
  
  	else l[i][j] = l[i][j-1] + 1;
  }
  }
  
  for(int i = 0; i < h; i++){
  for(int j = w-1; j >= 0; j--){
  	if(s[i][j] == '#') r[i][j] = 0;
    
    else if(j == w-1) r[i][j] = 1;
  
  	else r[i][j] = r[i][j+1] + 1;
  }
  }
  
  for(int i = 0; i < h; i++){
  for(int j = 0; j < w; j++){
  	if(s[i][j] == '#') u[i][j] = 0;
    
    else if(i == 0) u[i][j] = 1;
  
  	else u[i][j] = u[i-1][j] + 1;
  }
  }
  
  for(int i = h-1; i >= 0; i--){
  for(int j = 0; j < w; j++){
  	if(s[i][j] == '#') d[i][j] = 0;
    
    else if(i == h-1) d[i][j] = 1;
  
  	else d[i][j] = d[i+1][j] + 1;
  }
  }
  
  int ans = 0;
  
  for(int i = 0; i < h; i++){
  for(int j = 0; j < w; j++){
  	ans = max(ans, l[i][j]+r[i][j]+u[i][j]+d[i][j]-3);
  }
  }
  
  cout << ans << endl;
  //cout << l[0][1] << " " << r[0][1] << " " << u[0][1] << " " << d[0][1] << endl;
}

Measured memory_bytes: 67200
from operator import mul
from functools import reduce
import numpy as np
#def ConZ(i):
    #z_num = i+int(i*(i-1)/2)
    #return z_num
#def ConN(i):
    #n_num = int(i*(i-1)/2)
    #return n_num

def cmb(n):
    over = reduce(mul, range(n, n - 2, -1))
    under = reduce(mul, range(1,2 + 1))
    return over // under


S = input()[::-1]
keta = 1
A_num = 0
x = 0
mod = np.array([0]*2019)
mod[0] += 1
for i in range(len(S)):
    A_num += (int(S[i:i+1])*keta)%2019
    if A_num >= 2019:
        A_num = A_num%2019
    mod[A_num] +=1
    #keta*=10
    keta = keta * 10 % 2019
#print(mod)
#x += ConZ(mod[0])
#del mod[0]

#for j in range(len(mod)):
    #x+=cmb(mod[j])
#print(x)
print(int(np.sum(mod* (mod - 1) /2)))


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

using namespace std;

using ll = long long;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<string> s(n);
    vector<int> t(n);
    for (int i = 0; i < n; ++i) {
        cin >> s[i] >> t[i];
    }
    string x;
    cin >> x;

    bool f = false;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        if (f) ans += t[i];
        if (s[i] == x) f = true;
    }
    cout << ans << "\n";
    return 0;
}

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

using namespace std;
int main(){
  int i,n,a;
  vector <int> v;
  
  cin>>n;
  for(i=0;i<n;i++){
    cin>>a;
    v.push_back(a);
  }
  
  sort(v.begin(),v.end());
  cout<<v[n-1]-v[0]<<endl;
  return 0;
}

Measured memory_bytes: 256
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

import itertools
H, W, K = mi()

#hから、fr:左(-1), 真っ直ぐ(0), 右(1)から wに落ちてこれるような、h行の横棒の引き方は何種類あるかを返す
def howmany(fr, h, w):
  global W
  #領域外なので0を返す
  if w+fr==0 or w+fr==W+1: return 0
  #ここから先はちゃんと領域内から落ちてくる場合
  ans = 0
  #bit全探索。区間のbitにはstatus[0]~[W-2]でアクセス
  for status in itertools.product(('0','1'),repeat=W-1):
    #両端の区間を0で埋める（添字バグを回避するため
    status = ''.join(('0',''.join(status),'0')) #左から0011010みたいな感じで入ってる
    #wの左側の区間はw-1, 右側はwに対応している
    #1は横棒がある、0は横棒がない
    if '11' in status: continue
    elif fr==0:
      if status[w-1]=='1' or status[w]=='1': continue
    elif fr==1:
      if status[w]=='0': continue
    else: #fr==-1の場合
      if status[w-1]=='0': continue
    #これらをクリアした場合は条件を満たしていることになるのでans+=1
    ans += 1
  return ans % 1000000007

#DP[H行から]ストンと[W列に]落ちてくる場合の数
DP = [[0]*(W+2) for _ in range(H+1)]
DP[0][1] = 1

for h in range(1, H+1):
  for w in range(1, W+1):
  #DP[h][w]を求める。
  #まず、どこから落ちてくるか（最大3箇所）で3パターンに分ける。
    #1. まっすぐ落ちてくるパターン
    #まっすぐパターンは、「存在しない」が無いので、ifは要らない
    #DP[h-1][w]から落ちてくる
    DP[h][w] = ((DP[h-1][w-1] * howmany(-1, h, w))%1000000007 + (DP[h-1][w] * howmany(0, h, w))%1000000007 + (DP[h-1][w+1] * howmany(1, h, w))%1000000007)%1000000007

print(DP[H][K])



Measured memory_bytes: 42860
#include <bits/stdc++.h>
using namespace std;
#define inf 999999999
#define loop(i, a, b) for (int i = (a), i##len = (b); i < i##len; ++i)
#define rep(i, n) loop(i, 0, n)
#define lin long long
#define lfl long double

lin h,w;
bool a[1001][1001];

int main(void)
{
    vector<pair<lin, lin>> q;

    cin >> h >> w;
    rep(i,h)
    {
        string s;
        cin >> s;
        rep(j,w)
        {
            a[j][i] = s[j] == '#';
            if(a[j][i])
                q.push_back(make_pair(j,i));
        }
    }

    lin b = q.size();
    lin res = 0;
    vector<pair<lin, lin>> d;
    d.push_back(make_pair(1, 0));
    d.push_back(make_pair(-1, 0));
    d.push_back(make_pair(0, 1));
    d.push_back(make_pair(0, -1));

    while(b < h * w)
    {
        vector<pair<lin, lin>> qq;

        rep(i, q.size())
        {
            auto p = q[i];

            rep(j, d.size())
            {
                lin x = p.first + d[j].first;
                lin y = p.second + d[j].second;

                if(x < 0 || w <= x || y < 0 || h <= y)
                    continue;

                if(a[x][y])
                    continue;

                a[x][y] = true;
                qq.push_back(make_pair(x,y));
            }
        }

        b += qq.size();

        q = qq;
        res++;
        //cout << b << "," << res << endl;
    }

    cout << res << endl;

    return 0;
}


Measured memory_bytes: 25316
//bit全探索
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define pb push_back
using ll = long long;
using vin=vector<int>;
using vll=vector<ll>;
using vst=vector<string>;
using P = pair<int, int>;
const int inf=1e9+7;
const ll INF=1e18;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };

int keta(int x){
 int ret=0;
  while(x>0){
   ret+=x%10; 
    x/=10;
  }
  return ret;
}

int main(){cout<<fixed<<setprecision(10);
		   int n;
           cin>>n;
           int ans=inf;
           rep(i,1,n){
             int a=i;
             int b=n-i;
             chmin(ans,keta(a)+keta(b));
           }
           cout<<ans<<endl;
}

Measured memory_bytes: 3588
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>

//#include <tuple>

//#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define ll long long
#define pb push_back

int main() {
  int A, B;
  cin >> A >> B;
  int x;
  if (A < B) {
    x = B;
    B--;
  } else {
    x = A;
    A--;
  }
  
  x += max(A, B);
  cout << x << endl;

}


Measured memory_bytes: 256
package main

import (
    "fmt"
)

func main() {
    var n, k, h int
    count := 0
    fmt.Scanf("%d %d",&n, &k)

    for i := 0; i < n; i++{
        _, err := fmt.Scanf("%d", &h)
        if (nil != err) {
            break;
        }
        if h >= k {
            count ++
        }
    }
    fmt.Println(count)
}

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

int main(void){
    int n, a, b;
    cin >> n >> a >> b;
    int cnt[3] = {};
    rep(i,n) {
        int p;
        cin >> p;
        if (p <= a) cnt[0]++;
        else if (p <= b) cnt[1]++;
        else cnt[2]++;
    }
    cout << min({cnt[0], cnt[1], cnt[2]}) << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <iomanip>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define repr(e,x) for(auto& e:x)
using namespace std;
typedef long long ll;

const ll MOD=1000000007;

ll N;
ll A[100000];

int main(){
    cin>>N;
    rep(i,N) cin>>A[i];

    ll cnt0=3;
    vector<ll> cnt(N,0);
    ll ans=1;
    rep(i,N){
        if(A[i]==0){
            ans*=cnt0;
            cnt0--;
        }else{
            ans*=cnt[A[i]-1];
            cnt[A[i]-1]--;
        }
        cnt[A[i]]++;
        ans%=MOD;
    }
    ans+=MOD;
    ans%=MOD;

    cout<<ans<<endl;
}

Measured memory_bytes: 1792
# -*- coding: utf-8 -*-
data = input().split()

round = int(data[0])
cnt_house = int(data[1])

distance = input().split()

min_dist = None

for start in range(cnt_house):
  if start == 0:
    move_dist = int(distance[cnt_house - 1]) - int(distance[start])
  else:
    move_dist = (round - int(distance[start])) + int(distance[start - 1])
  
  if min_dist is None or min_dist > move_dist:
    min_dist = move_dist

print(min_dist)

Measured memory_bytes: 18484
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define for1(i, m, n) for (int i = m; i < n; i++)
#define ll long long
#define endl '\n'
using namespace std;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a, b;
    cin >> a >> b;
    int d = a /b;
    int r = a % b;
    double f = 1.0 * a / b;
    cout << d <<  " " << r << " ";
    printf("%lf\n", f);
    return 0;
}


Measured memory_bytes: 3356
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
typedef long long LL;
const LL N = 2005;
const LL M = 400005;

vector <LL> G[N];
LL vis[2][N][N],p[2][N],vi[N];
LL eu[M],ev[M],n,m;

void dfs_vis(LL u,LL rt){
	vis[0][rt][u] = 1;
	vi[u] = 1;
	for(LL i = 0;i < G[u].size();i ++){
		LL v = G[u][i];
		if(vi[v]) continue;
		dfs_vis(v,rt);
	}
}

void get_vis(){
	for(LL i = 1;i <= n;i ++){
		memset(vi,0,sizeof(vi));
		dfs_vis(i,i);
	}
}

void dfs_sol(LL u,LL col,LL pid,LL rt){
	p[pid][u] = col;
	vi[u] = 1;
	for(LL i = 0;i < G[u].size();i ++){
		LL v = G[u][i];
		if(vi[v]) continue;
		dfs_sol(v,col,pid,rt);
	}
}

void solve(LL u){
	memset(p,0,sizeof(p));
	memset(vi,0,sizeof(vi)); vi[u] = 1;
	for(LL i = 0;i < G[u].size();i ++) if(!vi[G[u][i]]) dfs_sol(G[u][i],i + 1,0,u);
	memset(vi,0,sizeof(vi)); vi[u] = 1;
	for(LL i = (LL)(G[u].size()) - 1;i >= 0;i --) if(!vi[G[u][i]]) dfs_sol(G[u][i],i + 1,1,u);
	for(LL i = 1;i <= n;i ++) if(vi[i] && p[0][i] != p[1][i]) vis[1][u][i] = 1;
}

int main(){
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for(LL i = 1;i <= m;i ++){
		cin >> eu[i] >> ev[i];
		G[eu[i]].push_back(ev[i]);
	}
	get_vis();
	for(LL i = 1;i <= n;i ++) solve(i);
	for(LL i = 1;i <= m;i ++) cout << ((vis[0][ev[i]][eu[i]] ^ vis[1][eu[i]][ev[i]]) ? "diff" : "same") << '\n';
	return 0;
}

Measured memory_bytes: 44800
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using ld = long double;
#define ALL(x) x.begin(),x.end()
#define P pair<int,int>
#define mod 1000000007

int main() {
  int n;
  cin >> n;
  cout << (1000 - n % 1000) % 1000 << endl;

  return 0;
}


Measured memory_bytes: 3632
#include <cstdio>
#include <cstdlib>
#include <cstdint>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <array>
#include <vector>
#include <unordered_map>
#include <unordered_set>

int main() {
    int A, B;
    std::cin >> A >> B;

    const int plus     = A + B;
    const int minus    = A - B;
    const int multiple = A * B;

    std::cout << std::max(plus, std::max(minus, multiple)) << std::endl;
    
    return 0;
}


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

int main(){ 
	string s1,s2,s3;
	cin>>s1>>s2>>s3;
	char A=s1[0]-32;
	char B=s2[0]-32;
	char C=s3[0]-32;
	cout<<A<<B<<C<<endl;
}

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

int main(){
  int x, y;
  cin >> x >> y;
  int i;
  for(i = 0; i <= x; i++){
    if(i*2 + (x-i)*4 == y){ break;}
  }
  if(i == x + 1){ cout << "No" << endl;}
  else{ cout << "Yes" << endl;}
}

Measured memory_bytes: 3648
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <queue>

#define mp make_pair
#define pb push_back


typedef long long ll;
typedef long double ld;

using namespace std;
const int MX = 10000;

int n, a;
ll dp[MX * 2];

int main() {
	cin >> n >> a;
	dp[MX] = 1;
	for (int it = 0; it < n; ++it) {
		int x;
		cin >> x;
		x -= a;
		if (x <= 0) {
			for (int j = -x; j < 2 * MX; ++j)
				dp[j + x] += dp[j];
		}
		else {
			for (int j = 2 * MX - x; j >= 0; --j)
				dp[j + x] += dp[j];
		}
	}
	cout << dp[MX] - 1 << "\n";
	return 0;
}




Measured memory_bytes: 512
s = input()
a = list(map(str, range(1, 10)))
b = list(map(str, range(0, 3)))
mm = 0
ba = 0
for i in [0, 2]:
    if s[i] == "0" and s[i+1] in a:
        mm += 1
        ba = i
    elif s[i] == "1" and s[i+1] in b:
        mm += 1
        ba = i
if mm == 0:
    print("NA")
elif mm == 1 and ba == 0:
    print("MMYY")
elif mm == 1 and ba == 2:
    print("YYMM")
elif mm == 2:
    print("AMBIGUOUS")

Measured memory_bytes: 3064
#include <stdio.h>

int main(){
	
	int inp1, inp2, inp3, o=0;
	
	scanf("%d %d %d", &inp1, &inp2, &inp3);
	for(int i=inp1; i<=inp2; i++){
		if(i%inp3==0){
			o++;
		}
	}
	printf("%d\n", o);
	
	
	return 0;
}

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

int main(){
    //input
    int H,W;
    cin >> H >> W;

    vector<string> grid(0);

    string s = string(W,'.');

    for(int i=0;i<H;i++){
        string str;
        cin >> str;
        if(str == s)continue;
        grid.push_back(str);
    }

    int v[W] = {0};
    for(int i=0;i<grid.size();i++){
        string str = grid.at(i);
        for(int j=0;j<str.size();j++){
            if(str.at(j) == '#') v[j] = 1;
        }
    }

    for(int i=0;i<grid.size();i++){
        string str = grid.at(i);
        for(int j=0;j<str.size();j++){
            if(v[j]) cout << str.at(j);
        }
        cout << endl;
    }

    return 0;
}

Measured memory_bytes: 256
from collections import deque
K=int(input())
que=deque([1,2,3,4,5,6,7,8,9])
for i in range(K):
    a=que.popleft()
    if not a%10==0:
        que.append(a*10+a%10-1)
    que.append(a*10+a%10)
    if not a%10==9:
        que.append(a*10+a%10+1)
print(a)

Measured memory_bytes: 11908
#define ll long long int
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <set>
using namespace std;
const ll y = 1000;
const ll INF = y*y*y*y*y*y;
int main() {
	string s, t;
	cin >> s >> t;
	int n1 = s.size();
	int n2 = t.size();
	vector <vector <int>> dp(n1 + 1, vector<int>(n2 + 1));
	for (int i = 1; i <= n1; i++) {
		for (int j = 1; j <= n2; j++) {
			dp[i][j] = max(dp[i][j-1], dp[i - 1][j]);
			if (s[i - 1] == t[j - 1]) { dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1); }
		}
	}
	string ans;
	int i=n1, j=n2;
	while (i != 0 && j != 0) {
		if (s[i - 1] == t[j - 1]) { ans += s[i - 1]; i--; j--; }
		else { if (dp[i - 1][j] == dp[i][j]) { i--; } else j--; }
	}
	reverse(ans.begin(), ans.end());
	cout << ans;
}

Measured memory_bytes: 35584
#include<bits/stdc++.h>
using namespace std;
#define debug(x) cout << '>' << #x << ':' << x << endl;
#define ll long long

int main() {
	string s, t;
	cin >> s >> t;
	char mins = 'z', maxt = 0;
	for (int i = 0; i < (int)s.size(); i++) {
		mins = min(mins, s[i]);
	}
	for (int i = 0; i < (int)t.size(); i++) {
		maxt = max(maxt, t[i]);
	}
	if (maxt > mins)
		return printf("Yes\n"), 0;
	else if (mins > maxt)
		return printf("No\n"), 0;
	else {
		if (t.size() > s.size()) {
			sort(s.begin(), s.end());
			sort(t.begin(), t.end());
			for (int i = 0; i < (int)s.size(); i++) {
				if (s[i] != t[i])
					return printf("No\n"), 0;
			}
			return printf("Yes\n"), 0;
		} else
			return printf("No\n"), 0;
	}
}


Measured memory_bytes: 3576
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e2+5;
const int INF = 0x3f3f3f3f;

int main( )
{
    std::ios::sync_with_stdio(0);cin.tie(0); 
	
	ll n,m;
	cin >> n >> m;
	printf("%lld\n",n*(n-1)/2+m*(m-1)/2);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define INF (1<<30)+100
using namespace std;

	
unsigned ll n, q, x;


int main()
{
	cin>>x;
	n=2;
	while(x--)
	{
		n+=(n+1)+1;
	}
	cout<<n<<'\n';
	return 0;
}


Measured memory_bytes: 256
s=list(input())
t=list(input())
x=len(s)
y=len(t)
for i in range(x-y+1):
    for j in range(y):
        if s[x-y-i+j]!=t[j] and s[x-y-i+j]!="?":
            break
    else: 
        s[x-y-i:x-i]=t
        print("".join(s).replace("?","a"))
        exit()
print("UNRESTORABLE")        

Measured memory_bytes: 3064
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
typedef long long lng;
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORD(i,b,a) for(int i=(b); i>=(a); --i)
#define REP(i,n) FOR(i,0,n-1)
#define ALL(a) (a).begin(), (a).end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end()) //ATTENTION: <a> must be sorted in advance

lng power(lng b, lng n) {lng sol=1; while(n>0) {if(n&1) {sol=sol*b;} n>>=1; b*= b;} return sol;} //calculate b^n

const int MOD = 1000000007; //10^9+7


/*********** variables ************/
string s;
/**********************************/

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

    int len = s.size();
    bool flg = false;
    FOR(c, 'a', 'z') {
        flg = true;
        REP(i, len) {
            if(c == s[i]) {
                flg = false;
                break;
            }
        }
        if(flg) {
            cout << char(c) << endl;
            return 0;
        }
    }
    cout << "None" << endl;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define int long long
#define ALL(v) (v).begin(),(v).end()
#define Vi vector<int>
#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repeq(i,a,b) for(int i=a;i<=b;i++)
#define repr(i,a,b) for(int i=a;i>b;i--)
#define repreq(i,a,b) for(int i=a;i>=b;i--)
#define leng(n) (int)(log10(n)+1)
#define INF 9000000000000000000
#define MOD 1000000007
#define PAI 3.14159265358979
// ver1.6
using namespace std;

int gcd(int a,int b){return b?gcd(b,a%b):a;}  //  最大公約数gcd
int lcm(int a,int b){return a/gcd(a,b)*b;}  //  最小公倍数lcm

signed main() {
  cout << fixed << setprecision(14);
  int n;
  cin >> n;
  Vi non0(0);
  int memo,sum = 0;
  
  rep(i,0,n){
    cin >> memo;
    sum += memo;
    if(memo%10!=0) non0.pb(memo);
  }
  if(non0.size()==0) {
    cout << 0 << endl;
    return 0;
  }
  if(sum%10!=0){
    cout << sum << endl;
    return 0;
  }
  sort(ALL(non0));
  cout << sum - non0[0] << endl;
  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
using ll = long long;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
#define REP(var, a, b) for (int var = (a); var < (b); var++)
#define rep(var, n) for (int var = 0; var < (n); ++var)
#define ALL(c) (c).begin(), (c).end()
#define rALL(c) (c).rbegin(), (c).rend()
ll MOD = 1000000007;
const ll INF = 1LL << 60;

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

  ll d;
  cin >> d;
  vl c(26);
  rep(i,26) cin>>c[i];
  vvl s(d, vl(26));
  rep(i,d) {
    rep(j,26) {
      cin >> s[i][j];
    }
  }

  vl last(26, 0);
  vl ans(d);
  vvl x(d, vl(26, 0));

  rep(i, d) {
    ll day = d + 1;
    vl cost(26, 0);
    vector<tuple<ll,ll,ll>> tmp(26);
    ll maxcost = -1;
    // ll sel = 0;
    rep(j, 26) {
      tmp[j] = {
        c[j] * (day - last[j]) + s[i][j],
        s[i][j],
        j
      };
    }
    sort(tmp.begin(), tmp.end(), [](const tuple<ll,ll,ll>& a, const tuple<ll,ll,ll>& b) {
      if (get<1>(a) > get<1>(b)) return true;
      if (get<1>(a) == get<1>(b) && get<0>(a) > get<0>(b)) return true;
      return false;
    });
    ll sel = get<2>(tmp[0]);
    last[sel] = day;
    ans[i] = sel;
    // cerr << sel + 1 << endl;
    x[i][sel] = 1;
  }

  random_device rd;  //Will be used to obtain a seed for the random number engine
  mt19937 gen(rd()); //Standard mersenne_twister_engine seeded with rd()
  uniform_int_distribution<> distrib(0, d-1);
  rep(t, 100000) {
    ll i = distrib(gen);
    vl duration1(26, 0), duration2(26, 0), duration(26, 0);
    ll sel = -1;
    rep(j, 26) {
      if (x[i][j] == 1) {
        sel = j;
        break;
      }
    }
    // cerr << i << "," << sel << endl;
    // cerr << sel << endl;
    rep(j, 26) {
      for (ll ii = i-1; ii >= 0; ii--) {
        if (x[ii][j] == 0) duration1[j]++;
        else break;
      }
      REP(ii, i+1, d) {
        if (x[ii][j] == 0) duration2[j]++;
        else break;
      }
      duration[j] = duration1[j] + duration2[j] + 1;
    }

    ll maxj = sel;
    ll maxdiff = 0;
    ll minus = s[i][sel] + c[sel] * ((duration[sel] + 1) * duration[sel] / 2 - (duration1[sel] + 1) * duration1[sel] / 2 - (duration2[sel] + 1) * duration2[sel] / 2);
    rep(j, 26) {
      if (j == sel) continue;
      ll plus = s[i][j] + c[j] * ((duration[j] + 1) * duration[j] / 2 - (duration1[j] + 1) * duration1[j] / 2 - (duration2[j] + 1) * duration2[j] / 2);
      if (plus > minus && plus - minus > maxdiff) {
        maxj = j;
        maxdiff = plus - minus;
      } 
    }
    if (maxj != sel) {
      x[i][maxj] = 1;
      x[i][sel] = 0;
    }
  }

  rep(i, d) {
    rep(j, 26) {
      if (x[i][j] > 0) {
        cout << j + 1 << endl;
        break;
      }
    }
  }
  return 0;
}


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

int main(){
    ll N;
    ll ans=0;
    ll mae,ato;

    cin>>N;
    cin>>mae;
    
    for(int i=1;i<N;i++){
        cin>>ato;
        if(mae>ato){
            ans+=mae-ato;
            //mae=mae;
        }else{
            mae=ato;
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3620
#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(), (x).end()
#define dbg(x) cerr << #x << ": " << x << endl

string sub(int x) {
  string res = "";
  rep(i, 6) {
    if(x > 0) {
      char c = '0' + (x % 10);
      res = c + res;
    } else {
      res = '0' + res;
    }
    x /= 10;
  }
  return res;
}

string prefid(int p) {
  return sub(p);
}

string cityid(int y) {
  return sub(y);
}

int main() {
  int n, m;
  cin >> n >> m;
  vector<P> cities(m);
  map<int, P> cnums;
  rep(j, m) {
    int p, y;
    cin >> p >> y;
    cities[j] = make_pair(p, y);
    cnums[j] = cities[j];
  }
  sort(all(cities));
  int cnt = 0;
  int prevp = cities[0].first;
  map<P, string> ids;
  rep(j, m) {
    P c = cities[j];
    if(prevp == c.first)
      cnt++;
    else {
      cnt = 1;
      prevp = c.first;
    }
    ids[c] = prefid(cities[j].first) + cityid(cnt);
  }
  rep(j, m) { cout << ids[cnums[j]] << endl; }
  return 0;
}

Measured memory_bytes: 19456
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef map<int,int> mii;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<long long> vl;
typedef vector<vector<ll>> vll;
typedef vector<bool> vb;
typedef set<int> si; 
typedef queue<int> qi;
typedef stack<int> sti;
typedef priority_queue<int> pqi;
#define fori(i,a,b) for(int i = (a); i < (b); ++i)
#define rep(i,b,a) for(int i = (b); i >= (a); --i)
#define all(a) (a).begin(), (a).end()
//#define __builtin_popcountll bitCountLL
//#define __builtin_popcount bitCount
//__builtin_ctz 末尾0的个数, __builtin_clz 前导0的个数
//__builtin_ffs 最后一个1的位置
#define maxn 100005
#define Mod 1000000007
const int INF = 2e9;
const ll ML = 4e18;
    
void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int w = 0, r = 0;
    fori(i,0,n) {
        if(s[i] == 'W') w++;
        else r++;
    }
    int ans = 0;
    fori(i,0,r) {
        if(s[i] == 'W') ans++;
    }
    cout << ans;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
	//cout.precision(30); cout << fixed;
	//freopen("D:\\data_in.txt", "r", stdin);
   
    solve();
   
    /*
    clock_t start,finish;
    start = clock();
    
    finish = clock();
    cout << "\n" << (double)(finish - start) / (double)(CLOCKS_PER_SEC) * 1000 << "ms" << endl;
    */
    return 0;
}

/***************************************************************
 question:
 idea:
 tag:
 record:
 ***************************************************************/


Measured memory_bytes: 3756
foo :: Int -> [Int] -> [Int]
foo x []     = []
foo x (n:ns) = x:foo next ns
  where next = 2 * n - x

bar :: [Int] -> Int
bar [] = 0
bar [x] = x
bar (x:y:ys) = x - y + bar ys

printList :: [Int] -> IO ()
printList ints = putStrLn $ unwords $ map show ints

main = do
  _ <- getLine
  nums <- map read . words <$> getLine :: IO [Int]
  printList $ foo (bar nums) nums


Measured memory_bytes: 55676
#include <cstdio>
#include <algorithm>
#include <array>
using namespace std;

int H, *A;  // H = heap size

void maxHeapify(int i) {
    int largest;
    int left = 2 * (i + 1) - 1;
    int right = 2 * (i + 1);
    if (left < H && A[left] > A[i]) {
        largest = left;
    } else {
        largest = i;
    }
    if (right < H && A[right] > A[largest]) {
        largest = right;
    }

    if (largest != i) {
        swap(A[i], A[largest]);
        maxHeapify(largest);
    }
}

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

    A = new int[H];
    for (int i = 0; i < H; i++) {
        scanf("%d", &A[i]);
    }
    
    for (int i = H / 2 - 1; i >= 0; i--) {
        maxHeapify(i);
    }

    for (int i = 0; i < H; i++) {
        printf(" %d", A[i]);
    }
    printf("\n");
    
    return 0;
}


Measured memory_bytes: 4552
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = Integer.parseInt(scanner.nextLine());
        String[] line = scanner.nextLine().split(" ", n);

        int total = 0;
        int cur = 0;
        for (int i = 0; i < n; i++) {
            int h = Integer.parseInt(line[i]);
            if (cur < h) {
                total += h - cur;
            }
            cur = h;
        }
        System.out.println(total);
    }
}


Measured memory_bytes: 21972