akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
// ------------------------
void solve() {
    string S; cin >> S;
    if(S[0] == 'S') cout << "Cloudy" << endl;
    if(S[0] == 'C') cout << "Rainy" << endl;
    if(S[0] == 'R') cout << "Sunny" << endl;
}

signed main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    solve();
    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define MAX 2000000
#define INFTY (1<<30)

int H, A[MAX + 1];

void maxHeapify(int i) {
	int l, r, largest;
	l = 2 * i;
	r = 2 * i + 1;
	if (l <= H && A[l] > A[i])
		largest = l;
	else
		largest = i;
	if (r <= H && A[r] > A[largest])
		largest = r;
	if (largest != i) {
		swap(A[i], A[largest]);
		maxHeapify(largest);
	}
}

int extract() {
	int maxv;
	if (H < 1)
		return -INFTY;
	maxv = A[1];
	A[1] = A[H--];
	maxHeapify(1);
	return maxv;
}

void increaseKey(int i, int key) {
	if (key < A[i])
		return;
	A[i] = key;
	while (i > 1 && A[i / 2] < A[i]) {
		swap(A[i], A[i / 2]);
		i = i / 2;
	}
}

void insert(int key) {
	H++;
	A[H] = -INFTY;
	increaseKey(H, key);
}

int main() {
	int key;
	char com[10];
	while (1) {
		scanf("%s", com);
		if (com[0] == 'e' && com[1] == 'n')
			break;
		if (com[0] == 'i') {
			scanf("%d", &key);
			insert(key);
		} else {
			printf("%d\n", extract());
		}
	}
	return 0;
}

Measured memory_bytes: 7120
[<AutoOpen>]
module Program

open System

let read f = stdin.ReadLine() |> f
let reads f = stdin.ReadLine().Split() |> Array.map f

[<EntryPoint>]
let main argv =
    let [|a;p|] = reads int
    printfn "%i" ((3 * a + p) / 2)
    0

Measured memory_bytes: 14044
import math

K = int(input())
S = 0

for i in range(1,K-1):
    for j in range(i+1,K):
        for k in range(j+1,K+1):
            S += math.gcd(i,math.gcd(j,k))

S *= 6

T = 0

for i in range(1,K):
    for j in range(i+1,K+1):
        T += math.gcd(i,j)

T *= 6

U = (K*(K+1))//2

#print(S,T,U)
print(S+T+U)

Measured memory_bytes: 9204
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define IO std::ios::sync_with_stdio(false);std::cin.tie(0)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define mset(s,_) memset(s,_,sizeof s)
#define fi first
#define se second
#define pb push_back
map<string,int>mp;
int main(){
	int n;
	cin>>n;
	int ans=0;
	rep(i,1,n){
		string s;
		cin>>s;
		mp[s]++;
		if(mp[s]==1) ans++;
	}
	cout<<ans<<'\n';
}

Measured memory_bytes: 19116
#include<bits/stdc++.h>
using namespace std;
string s;
int main()
{
    cin>>s;
    for(int i=0;i<s.length();i++)
    {
        if(s[i]=='C')
        {
            for(int j=i+1;j<s.length();j++)
            {
                if(s[j]=='F')
                {
                    cout<<"Yes"<<endl;
                    return 0;
                }
            }
        }
    }
    cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <vector>
#include <cstdlib>
#include <list>
#define _USE_MATH_DEFINES
#include <math.h>

using namespace std;

int main() {

	int A, B, C, D;

	cin >> A >> B >> C >> D;
	if (A*B > C*D)
		cout << A*B << endl;
	else
		cout << C*D<< endl;


	return 0;
}

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

int main() {
  ll n;
  cin >>n;
  vector<ll> a(n+1),b(n+1),a2(n+1);
  ll nl=0;//葉の数
  rep(i,n+1) {
    cin >>a[i];
    nl+=a[i];
  }
  if(a[0]>1){
    cout<<-1<<endl;
    return 0;
  }
  
  b[0]=1-a[0];
  ll ans=1;
  nl-=a[0];
  rep(i,n){
    nl-=a[i+1];//a[i+2]以降の葉の数．
    if(a[i+1]>b[i]*2){
      cout<<-1<<endl;
      return 0;
    }
 
    b[i+1]=min(nl, 2*b[i]-a[i+1]);
    ans+=b[i+1]+a[i+1];
  }
  
  cout<<ans<<endl;
  return 0;
  
  
  
  
}


Measured memory_bytes: 5636
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
long long _read() {
	long long ans, c, x = 1;
	for (c = getchar(); c != '-' && (c<'0' || c>'9'); c = getchar());
	if (c == '-') x = -1, c = getchar();
	for (ans = 0; c <= '9'&&c >= '0'; c = getchar()) ans = ans * 10 + c - '0';
	return ans * x;
}
void _write(long long ans) {
	if (ans == 0) putchar('0');
	if (ans < 0) putchar('-'), ans = -ans;
	long long a[20], i;
	for (i = 1; ans; i++, ans /= 10) a[i] = ans % 10;
	for (i--; i; i--) putchar(a[i] + '0');
}
queue<int> q;
int n, ans = 0;
int a[1000001];
int t[1000001];
int main() {
	n = _read(); char c = getchar();
	for (; c<'a' || c>'z'; c = getchar());
	for (int i = 1; i <= n; i++, c = getchar()) a[i] = c;
	for (; c<'a' || c>'z'; c = getchar());
	for (int i = 1; i <= n; i++, c = getchar()) t[i] = c;
	for (int i = 1; i <= n; i++)
		if (a[i] != t[i]) break; else
			if (i == n) {
				puts("0");
				return 0;
			}
	for (int i = n, pos = n; i; i--) {
		if (t[i] == t[i - 1]) continue;
		for (pos = min(pos, i); pos&&a[pos] != t[i]; pos--);
		if (!pos) {
			puts("-1");
			return 0;
		}
		while (q.size() && q.front() - q.size() >= i) q.pop();
		q.push(pos);
		if (pos != i && q.size() > ans) ans = q.size();
	}
	_write(ans + 1); putchar('\n');
	return 0;
}

Measured memory_bytes: 12160
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();
		int C = sc.nextInt();
		if(C + B > A) {
			C = C- (A-B);
			System.out.println(C);
		}else {
			System.out.println(0);
		}

		sc.close();
	}

}


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

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

	int l[n];
	int sum = 0, cnt = 1;
	for (int i = 0; i < n; i++) {
		cin >> l[i];
		sum += l[i];
		if (sum <= x) {
			cnt++;
		}
	}

	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 256
import math
n =int(input())
h= list(map(int,input().split()))
dp=[0]*n
dp[1]=abs(h[1]-h[0])
for i in range(2,n):
    dp[i]=min( dp[i-2]+abs(h[i]-h[i-2]), dp[i-1]+abs(h[i]-h[i-1]) )
print(dp[n-1])

Measured memory_bytes: 14104
#include <iostream>
#include <sstream>
#include <stdio.h>
#include <stack>
#include <string>
#include <stdlib.h>

using namespace std;

void solve()
{
	string str;
	while(getline(cin, str))
	{
		stack<double> digits;
		stringstream ss(str);
		string temp;
		while(ss >> temp)
		{
			if(temp == "+" || temp == "-" || temp == "*" || temp == "/")
			{
				double n1, n2;
				n2 = digits.top();
				digits.pop();
				n1 = digits.top();
				digits.pop();
				if(temp == "+")
				{
					digits.push(n1 + n2);
				}
				else if(temp == "-")
				{
					digits.push(n1 - n2);
				}
				else if(temp == "*")
				{
					digits.push(n1 * n2);
				}
				else if(temp == "/")
				{
					digits.push(n1 / n2);
				}
			}
			else
			{
				digits.push(atof(temp.c_str()));
			}
		}
		printf("%.6f\n", digits.top());
	}
}

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

Measured memory_bytes: 1276
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int k,n,i,saidai=0;
  cin>>k>>n;
  int a[n];
  cin>>a[0];
  for(i=1;i<n;i++){
    cin>>a[i];
    saidai=max(saidai,a[i]-a[i-1]);
  }
  saidai=max(saidai,a[0]+k-a[n-1]);
  k-=saidai;
  cout<<k;
}

Measured memory_bytes: 1024
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    H,W = map(int, input().split())
    h,w = map(int, input().split())
    print(H*W-h*W-w*H+h*w)

if __name__ == '__main__':
    main()

Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define vi vector<int>
#define mod 1000000007
#define tc(t) 			int t;cin >> t;while(t--)
#define for0(i , n)		for(int i=0;i<n;i++)
#define loop(i , a, b)	for(int i=a;i<=b;i++)
#define endl '\n'

vector<int> dp(100001,-1);

int forgA(int ind , int n, int a[]){
	if(ind == n-1){
		return 0;
	}

	if(dp[ind] != -1){
		return dp[ind];
	}

	int c1 = abs(a[ind+1] - a[ind]) + forgA(ind+1,n,a);
	int c2 = INT_MAX;
	if(ind+2 <= n-1){
		c2 = abs(a[ind+2]-a[ind]) + forgA(ind+2,n,a);
	}

	return dp[ind] = min(c1,c2);
}

signed main() {

	ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
#ifndef ONLINE_JUDGE
	freopen("input.txt" , "r" , stdin);
	freopen("output.txt" , "w" , stdout);
#endif

	int n;
	cin >> n;
	int a[n];

	for0(i,n){
		cin >> a[i];
	}

	cout << forgA(0,n,a) << endl;
	return 0;
}

Measured memory_bytes: 12664
// Example program
#include <iostream>
using namespace std;
 
int main(){
  long long   n,x,y,z,a;
  
  cin >> n;
  cin >> a;
  x = a;
  y = a;
  z = a;
  n --;
  while(n > 0){
      cin >> a;
      z = z + a;
      if (x > a){
          x = a;
      } else if(y < a){
          y = a;
      }
      n--;
  }
  cout << x << " " << y << " " << z << endl;
  return 0;		 
}
		   





Measured memory_bytes: 3068
import java.util.Scanner;

class Main{
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);


		int[] aa=new int[100001];
		long[] souwa=new long[100001];
		long[] kousu=new long[100001];

		for(int i=0; i<100001; i++) {
			aa[i]=i;
			souwa[i]=0;
			kousu[i]=0;
		}

		int N=sc.nextInt();
		long K=sc.nextLong();
		long tmp1=0,tmp2=0;
		for(int i=0; i<N; i++) {
			tmp1=sc.nextLong();
			tmp2=sc.nextLong();
			kousu[(int) tmp1]+=tmp2;
		}
		souwa[0]=0;
		for(int i=1; i<=100000; i++) {
			souwa[i]=souwa[i-1]+kousu[i];
		}
		long kagen=0;
		long jyoge=0;

		for(int i=1; i<=100000; i++) {
			kagen=souwa[i-1]+1;
			jyoge=souwa[i];
			if(jyoge==0) {
				kagen=0;
			}
			else if(kagen==1) {
				kagen=0;
			}

			if(kagen<=K && K<=jyoge) {
				System.out.println(i);
				System.exit(0);
			}
		}
	}
}

Measured memory_bytes: 80780
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
int dp[1005][1005];
int main()
{
  int h,w;
  char a[1005][1005];
  cin>>h>>w;

  dp[1][1]=1;

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

  for(int i=1; i<=h; i++){
    for(int j=1; j<=w; j++){
      if(a[i][j]!='#'){
	dp[i][j]+=(dp[i-1][j]%MOD+dp[i][j-1]%MOD)%MOD;
      }
    }
  }

  cout<<dp[h][w]<<'\n';
  return 0;
}


Measured memory_bytes: 5120
//#include<bits/stdc++.h>
#include<iostream>
#include<vector>
#include<algorithm>
#define INF 2147483647
#define lli long long int
#define MOD 1000000007
#define pb push_back

using namespace std;
typedef vector<int> vi;
typedef vector< vector<int> > vvi;
typedef pair<int,int> pii;
typedef vector<pair<int,int>> vpii;



int main() {

	int n; cin >> n;
	vi fac;

	cout << n << ":";
	for (int i = 2; i * i <= n; i++) {
		while(n % i == 0) {
			fac.pb(i);
			n = n / i;
		}
	}
	if (n != 1) fac.pb(n);
	
	for (int i  = 0; i < fac.size(); i++) {
		cout << " " << fac[i];
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 3148
#include <stdio.h>
#include <iostream>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <list>
#include <utility>
#include <set>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <bitset>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <random>

using namespace std;

static const double EPS = 1e-9;
template<class T> bool INRANGE(T x,T a,T b){return a<=x&&x<=b;}
template<class T> void amin(T &a,T v){if(a>v) a=v;}
template<class T> void amax(T &a,T v){if(a<v) a=v;}
int ROUND(double x) { return (int)(x+0.5); }
bool ISINT(double x) { return fabs(ROUND(x)-x)<=EPS; }
bool ISEQUAL(double x,double y) { return fabs(x-y)<=EPS*max(1.0,max(fabs(x),fabs(y))); }
double SQSUM(double x,double y) { return x*x+y*y; }
#define PI  (acos(-1))
#define ARRAY_NUM(a) (sizeof(a)/sizeof(a[0])) 
#define NG (-1)
#define BIG ((int)1e9+10)
#define BIGLL ((ll)4e18)
#define SZ(a) ((int)(a).size())
#define SQ(a) ((a)*(a))
typedef unsigned long long ull;
typedef long long ll;

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

	for (int y = 0; y < H; ++y)
	{
		for (int x = 0; x < W; ++x)
		{
			string s;
			cin >> s;
			if (s == "snuke")
			{
				char a = 'A'+x;
				char b = 1+y;
				printf("%c%d\n",a,b);
				break;

			}

		}
	}



	return 0;
}


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

using namespace std;

int main(){
    const int INF = 1e9;

    int n;
    cin >> n;
    vector<array<int64_t, 2>> A(n);
    for (auto &a: A)
        cin >> a[0] >> a[1];

    sort(A.begin(), A.end());
    if (n == 2){
        cout << A[0][1] - A[0][0] + A[1][1] - A[1][0] + 2 << endl;
        return 0;
    }

    vector<int64_t> front(n - 1), back(n - 1);

    int64_t r = 1e9, l = 0;
    for (int i = 0; i < n - 1; i++){
        r = min(r, A[i][1]);
        l = max(l, A[i][0]);
        front[i] = max(0L, r - l + 1);
    }

    r = 1e9, l = 0;
    for (int i = n - 1; i > 0; i--){        r = min(r, A[i][1]);
        l = max(l, A[i][0]);
        back[i - 1] = max(0L, r - l + 1);
    }

    int64_t ans = 0;
    for (int i = 0; i < n - 1; i++)
        ans = max(ans, front[i] + back[i]);
    
    int maxi = 0;
    int ma = 0;
    for (int i = 0; i < n; i++){
        if (ma < A[i][1] - A[i][0]){
            ma = A[i][1] - A[i][0];
            maxi = i;
        }
    }
  
    int64_t max_l = 0, min_r = 1e9;
    for (int i = 0; i < n; i++){
        if (i == maxi)
            continue;
        max_l = max(max_l, A[i][0]);
        min_r = min(min_r, A[i][1]);
    }
  
    ans = max(ans, ma + 1 + max(0L, min_r - max_l + 1));
  
    cout << ans << endl;
}



Measured memory_bytes: 3328
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <unordered_map>
using namespace std;


class Desks{
public:
  int getMaxBooks(int n, int m, int k, vector<int>&a,vector<int>&b){
    unordered_map<int,int>aBooks;
    int nxtBInd = 0;
    long long timeUsed = 0LL;
    for(int i=0;i<n;i++){
      timeUsed += (long long)a[i];
    }
    for(int i=n;i>=0;i--){
      if(i<n){
	timeUsed -= (long long)a[i];
      }
      if(timeUsed<=k){
	long long newTU = timeUsed;
	while(nxtBInd<m){
	  newTU += (long long)b[nxtBInd];
	  if(newTU>k){
	    break;
	  }
	  nxtBInd++;
	}
	if(nxtBInd<m){
	  timeUsed = newTU-b[nxtBInd];
	}
	aBooks[i] = i+nxtBInd;
      }else{
	aBooks[i] = -1;
      }
    }
    unordered_map<int,int>::iterator it;
    int maxV = 0;
    for(it=aBooks.begin();it!=aBooks.end();it++){
      int nb = it->second;
      if(nb>maxV)maxV = nb;
    }
    return maxV;
  }
};
vector<string>split(string s, char delim){
  int len = s.length();
  string currStr = "";
  vector<string>retVec;
  for(int i = 0;i<len;i++){
    char ch = s[i];
    if(ch==delim){
      retVec.push_back(currStr);
      currStr = "";
    }else{
      currStr += ch;
    }
  }
  retVec.push_back(currStr);
  return retVec;
}


vector<int>strToIntVec(string s){
  int len = s.length();
  vector<string>strVec = split(s,' ');
  vector<int>retVec;
  for(int i=0;i<strVec.size();i++){
    int el = atoi(strVec[i].c_str());
    retVec.push_back(el);
  }
  return retVec;
}

int main(int argc, const char*argv[]){
  Desks d;
  string nmkLn,aLn,bLn;
  getline(cin,nmkLn);
  getline(cin,aLn);
  getline(cin,bLn);
  vector<int>a = strToIntVec(aLn);
  vector<int>b = strToIntVec(bLn);
  vector<int>nmkVec = strToIntVec(nmkLn);
  int nb = d.getMaxBooks(nmkVec[0],nmkVec[1],nmkVec[2],a,b);
  cout<<nb<<endl;
  return 0;
}


Measured memory_bytes: 27444
#include <bits/stdc++.h>
#define all(a) (a).begin(),(a).end()
#define rep(i,n) for(ll i=0,i##_len=(n);i<i##_len;i++)
#define rep2(i,a,b) for(ll i=(a),i##_len=(b);i<=i##_len;i++)
#define rrep(i,n) ll i=(n);ll now=-1;while(i--&&(now++||1))
#define Yes(n) cout<<((n)?Yes:No)
#define vll vector<ll>
#define mpll map<pair<ll,ll>,ll>
#define mp make_pair
#define pb push_back

using namespace std;
using ll = long long;

static inline void ignore_ret(int x) {x++;}
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(a>b){a=b;return true;}return false;}
template<class T> T gcd_vec(vector<T>v){T r=v.at(0);for(T i=1;i<v.size();i++)r=gcd(r,v.at(i));return r;}
template<class T> T lcm_vec(vector<T>v){T r=v.at(0);for(T i=1;i<v.size();i++)r=lcm(r,v.at(i));return r;}
template<class T> T factorial(T n){if(n==0)return 1;T r=1;for(T i=2;i<=n;i++)r*=i;return r;}
template<class T> T nCr(T n,T k){T r=1;k=min(k,n-k);for(T i=n-k+1;i<=n;i++)r*=i;return r/factorial(k);}
template<class T> T dot_product(vector<T>u,vector<T>v){T r=0;for(T i=0;i<u.size();i++)r+=u.at(i)*v.at(i);return r;}
template<class T> T sum(vector<T>v){return reduce(all(v),0LL);}

// Template ends here
double distance(ll i, ll j, mpll &map, vll x, vll y) {
    auto it = map.find(mp(i, j));
    if (it != map.end()) return it->second;
    else {
        double d = sqrt(pow(x.at(i) - x.at(j), 2) + pow(y.at(i) - y.at(j), 2));
        map.emplace(mp(i, j), d);
        return d;
    }
}

void solve(ll N, vector<ll> x, vector<ll> y){
    mpll map = {};
    double ans = 0;

    rep(i, N) {
        rep(j, N) {
            if (i == j) continue;
            ans += distance(i, j, map, x, y);
        }
    }

    cout << setprecision(10) << ans / double(N) << "\n";
}

int main() {
    ll N;
    ignore_ret(scanf("%lld",&N));
    vector<ll> x(N);
    vector<ll> y(N);
    for(int i = 0 ; i < N ; i++){
        ignore_ret(scanf("%lld",&x[i]));
        ignore_ret(scanf("%lld",&y[i]));
    }
    solve(N, move(x), move(y));
    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

class Edge{
public:
	ll to,weight;
	bool use{true};
	Edge(ll t,ll w):to(t),weight(w){}
};

class Edge2{
public:
	ll from,to,weight;
	Edge2()=default;
	Edge2(ll f,ll t,ll w):from(f),to(t),weight(w){}
};

class ConnectNodeInfo{
	vector<vector<Edge>> graph;
public:
	ConnectNodeInfo(int node_num){
		graph.resize(node_num);
	}
	void AddNonDirectionalConnection(ll u,ll v,ll w){
		graph[u].emplace_back(v,w);
		graph[v].emplace_back(u,w);
	}
	void AddDirectionalConnection(ll u,ll v,ll w){
		graph[u].emplace_back(v,w);
	}
	vector<Edge>& operator[](ll index){
		return graph[index];
	}
	size_t size(){return graph.size();}
};

class SearchPath{
	set<ll> visit;

	bool CanReachImpl(int start,int end,ConnectNodeInfo& connect){
		bool reach=false;
		if(start==end) return true;

		for(int i=0,ei=connect[start].size();i<ei;i++){
			if(!connect[start][i].use) continue;
			auto res = visit.emplace(connect[start][i].to);
			if(!res.second) continue;
			reach |= CanReachImpl(connect[start][i].to,end,connect);
		}
		return reach;
	}
public:
	bool CanReach(int start,int end,ConnectNodeInfo& connect){
		visit.clear();
		visit.emplace(start);
		return CanReachImpl(start,end,connect);
	}
};

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

	int N=in();
	vector<vector<int>> C(N,vector<int>(N));
	ConnectNodeInfo connect(N);
	vector<Edge2> edge;
	REP(i,N){
		REP(j,N){
			C[i][j]=in();
		}
	}
	REP(i,N){
		for(int j=i;j<N;j++){
			int v=C[i][j];
			if(v!=-1){
				connect.AddNonDirectionalConnection(i,j,v);
				edge.emplace_back(i,j,v);
			}
		}
	}
	sort(ALL(edge),[](Edge2& l,Edge2& r){return l.weight>r.weight;});
	SearchPath sp;
	int M=edge.size();
	ll sum=0;
	REP(i,M){
		auto& e=edge[i];
		for(auto& x:connect[e.from]){
			if(x.to==e.to) x.use=false;
		}
		for(auto& x:connect[e.to]){
			if(x.to==e.from) x.use=false;
		}
		if(!sp.CanReach(e.from,e.to,connect)){
			for(auto& x:connect[e.from]){
				if(x.to==e.to) x.use=true;
			}
			for(auto& x:connect[e.to]){
				if(x.to==e.from) x.use=true;
			}
			sum+=e.weight;
		}
	}
	
	out(sum);
	return 0;
}



Measured memory_bytes: 3424
#include <bits/stdc++.h>
using namespace std;
#define ri register int
namespace io {
	const int SIZE = (1 << 21) + 1;
	char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
	// getchar
	#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
	// print the remaining part
	inline void flush () {
		fwrite (obuf, 1, oS - obuf, stdout);
		oS = obuf;
	}
	// putchar
	inline void putc (char x) {
		*oS ++ = x;
		if (oS == oT) flush ();
	}
	// input a signed integer
	template <class I>
	inline void gi (I &x) {
		for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
		for (x = 0; c <= '9' && c >= '0'; c = gc()) x = (x << 1) + (x << 3) + (c & 15); x *= f;
	}
	// input a letter
	template <class I>
	inline void get (I &x) {
		for (c = gc(); c < 'A' || c > 'Z'; c = gc()) ;
		x = c;
	}
	// input a string
	inline void read (char *s){
		for(c = gc(); c < 'A' || c > 'Z'; c = gc()) ;
		for(; c >= 'A' && c <= 'Z'; c = gc()) *++s = c;
		*++s = '\0';
	}
	// print a signed integer
	template <class I>
	inline void print (I x) {
		if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
		while (x) qu[++ qr] = x % 10 + '0',  x /= 10;
		while (qr) putc (qu[qr --]);
	}
	//no need to call flush at the end manually!
	struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: gi;
using io :: get;
using io :: read;
using io :: putc;
using io :: print;
const int N=2e5+5;
int n,m,a[N],s[N],b[N];
struct segtree{
	#define lc x<<1
	#define rc x<<1|1 
	int tag[N<<4],val[N<<4];
	inline void push(ri x){
		tag[x]=1;
		val[x]=0;
	}
	inline void clear(){
		push(1);
	}
	inline void down(ri x){
		if(tag[x])
			push(lc),
			push(rc),
			tag[x]=0;
	}
	inline void upd(ri x,ri l,ri r,ri p,ri k){
		if(l==r){
			val[x]+=k;
			return;
		}
		ri mid=l+r>>1;
		down(x);
		p<=mid?upd(lc,l,mid,p,k):upd(rc,mid+1,r,p,k);
	}
	inline void cover(ri x,ri l,ri r,ri ql,ri qr){
		if(ql<=l&&r<=qr){
			push(x);
			return;
		}
		ri mid=l+r>>1;
		down(x);
		if(ql<=mid) cover(lc,l,mid,ql,qr);
		if(qr> mid) cover(rc,mid+1,r,ql,qr);
	}
	inline int query(ri x,ri l,ri r,ri p){
		if(l==r) return val[x];
		ri mid=l+r>>1;
		down(x);
		return p<=mid?query(lc,l,mid,p):query(rc,mid+1,r,p);
	}
}seg;
inline bool check(ri mid){
//	printf("mid = %d\n",mid);
	ri i,now;
	seg.clear();
	for(i=2;i<=n;++i){
		if(s[i-1]<s[i]) continue;
		now=s[i];
		while(now&&seg.query(1,1,m,now)==mid-1) --now;
		if(!now) return false;
		seg.upd(1,1,m,now,1);
		if(now+1<=m)
			seg.cover(1,1,n,now+1,m);
	}
	return true;
}
int main(){
	ri i,l,r,mid,lst;
	gi(n);
	for(i=1;i<=n;++i) gi(s[i]);
	for(i=1;i<=n;++i) a[i]=s[i];
	sort(a+1,a+1+n); 
	lst=0;
	for(i=1;i<=n;++i)
		if(a[i]!=a[i-1])
			b[i]=min(a[i],b[lst]+i-lst),
			lst=i;
	for(i=1;i<=n;++i) s[i]=b[lower_bound(a+1,a+1+n,s[i])-a];
	m=n;
//	for(i=1;i<=n;++i) printf("%d ",s[i]); puts("");
//	return 0;
	l=1;r=n;
	while(l<=r){
		mid=l+r>>1;
		if(check(mid))
			r=mid-1;
		else
			l=mid+1;
	}
	printf("%d\n",r+1);
	return 0;
}

Measured memory_bytes: 15232
//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_7_A

#include <iostream>
using namespace std;

void grade(int m, int f, int r){
  if((m == -1 || f == -1) || m+f < 30) cout << "F" << endl;
  else{
    if(m+f >= 80) cout << "A" << endl;
    else{
      if(m+f < 80 && m+f >= 65) cout << "B" << endl;
      else{
        if(m+f < 65 && m+f >= 50) cout << "C" << endl;
          else{
          if(m+f < 50 && m+f >= 30) {
              if(r >= 50)  cout << "C" << endl;
              else cout << "D" << endl;
          }
        }
      }
    }
  }
}

int main(){
  int m,f,r;
  //??????????¨?????????° m?????????????¨?????????° f??????????¨?????????° r
  while(cin >> m >> f >> r){
    if(m == -1 && f == -1 && r == -1) break;
    else grade(m,f,r);
  }
}

Measured memory_bytes: 1152
#include<stdio.h>
#define MAX 1000
#define VMAX 10000
#define TRUE 1
#define FALSE 0
 
int n,A[MAX],s;
int B[MAX],T[VMAX+1];
void sort(){
  int j,i,v;
  for(i=1;i<n;i++){
    v=B[i];
    j=i-1;
    while(j>=0 && B[j]>v){
      B[j+1]=B[j];
      j--;
    }
    B[j+1]=v;
  }
}
int smini(int x,int y){
  if(x>y)return y;
  else return x;
}
int solve(){
  int ans=0,V[MAX],i;
  int cur,S,m,an,v;
  for(i=0;i<n;i++){
    B[i]=A[i];
    V[i]=FALSE; // 0
  }
  sort();
  for(i=0;i<n;i++)T[B[i]]=i;
  for(i=0;i<n;i++){
    if(V[i])continue;
    cur=i;
    S=0;
    m=VMAX;
    an=0;
    while(1){
      V[cur]=TRUE;
      an++;
      v=A[cur];
      m=smini(m,v);
      S+=v;
      cur=T[v];
      if(V[cur])break;
    }
    ans+=smini(S+(an-2)*m,m+S+(an+1)*s);
}
  return ans;
}



int main(){
  int i,ans;
  scanf("%d",&n);
  s=VMAX;
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
    s=smini(s,A[i]);//minimam
}
  ans=solve();
  printf("%d\n",ans);

  return 0;
}

Measured memory_bytes: 616
/**
 *      ABC 47 C
 *      author  : kyomukyomupurin
 *      created : 2018-10-01 17:12:28
**/

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

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

    int count = 0;

    for (auto i = 0; i < (int) S.size() - 1; ++i) {
        if (S[i] != S[i + 1]) ++count;
    }
    cout << count << '\n';
    
    return 0;
}

Measured memory_bytes: 512
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	sc.Split(bufio.ScanWords)
	n, t, a := nextInt(), 500*nextInt(), 500*nextInt()
	h := nextInts(n)
	ans := 1
	min := abs(t - h[0]*3 - a)
	for i := 1; i < n; i++ {
		deg := abs(t - h[i]*3 - a)
		if deg < min {
			min = deg
			ans = i + 1
		}
	}
	puts(ans)
	wt.Flush()
}

var (
	sc  = bufio.NewScanner(os.Stdin)
	rdr = bufio.NewReaderSize(os.Stdin, 1000000)
	wt  = bufio.NewWriter(os.Stdout)
)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	i, _ := strconv.Atoi(next())
	return i
}

func nextFloat64() float64 {
	f, _ := strconv.ParseFloat(next(), 64)
	return f
}

func nextInts(n int) []int {
	slice := make([]int, n)
	for i := 0; i < n; i++ {
		slice[i] = nextInt()
	}
	return slice
}

func nextFloat64s(n int) []float64 {
	slice := make([]float64, n)
	for i := 0; i < n; i++ {
		slice[i] = nextFloat64()
	}
	return slice
}

func nextMega() string {
	buf := make([]byte, 0, 1000000)
	for {
		l, p, _ := rdr.ReadLine()
		buf = append(buf, l...)
		if !p {
			break
		}
	}
	return string(buf)
}

func putf(format string, a ...interface{}) {
	fmt.Fprintf(wt, format, a...)
}

func puts(a ...interface{}) {
	fmt.Fprintln(wt, a...)
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}


Measured memory_bytes: 640
n = int(input())
x = 1
y = 1
z = 1
a = [0]*(10**5)
for j in range(x,101):
    for k in range(y,101):
      for l in range(z,101):
        a[j**2+k**2+l**2+j*k+k*l+l*j]+=1
for i in range(1,n+1):
  print(a[i])

Measured memory_bytes: 9820
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <map>
#include <cstdio>
#include <math.h>
using namespace std;

#define ll long long
#define vecint vector<int>
#define listint list<int>
#define Pii pair<int, int>

#define REP(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define print(a) cout << a << endl

#define MOD 1000000007
#define NIL -1


int main(){
  string s;
  cin>>s;
  int ans=0;
  rep(i,s.size()){
    if(i%2==0){
      if(s[i]=='p') ans--;
    }else{
      if(s[i]=='g') ans++;
    }
  }

  print(ans);

  return 0;
}


Measured memory_bytes: 512
N = int(input())
H = [int(s) for s in input().split()]

if N == 1:
    print("Yes")
    exit()

H[0] -= 1
for i in range(1, N):
    if H[i-1] < H[i]:
        H[i] -= 1
    if H[i-1] > H[i]:
        print("No")
        exit()
print("Yes")


Measured memory_bytes: 15012
N = int(input())
T,A = list(map(int,input().split()))
H = list(map(int,input().split()))
MinDif = 1000
for i in range(N):
  Temp = T - H[i] * 0.006
  if abs(Temp - A) == min( MinDif, abs(Temp - A) ):
    MinDif = abs(Temp - A)
    ans = i + 1
print(ans)

Measured memory_bytes: 9216
N=int(input())
num_list=[int(i) for i in input().split()]
B=[None]*N
def counting(A,B,k):
    C = [0] * k
    for j in range(N):
        C[A[j]]+=1
    for i in range(1,k):
        C[i]+=C[i-1]
    for j in range(N-1,-1,-1):
        B[C[A[j]]-1]=A[j]
        C[A[j]]-=1
    return B
ans=counting(num_list,B,10000)
print(*ans)


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

int main() {
    

    // cinを高速にするためのおまじない
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    //Write code below
    
    int n;
    
    cin >> n;
    
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
      cin >> a.at(i);
    }
    
    vector<int> b(n);
    for (int i = 0; i < n; i++) {
      cin >> b.at(i);
    }
    
    vector<int> c(n - 1);
    for (int i = 0; i < n - 1; i++) {
      cin >> c.at(i);
    }
    
    int answer = 0;
    
    for (int i = 0; i < n; i++) {
        answer += b.at(a.at(i) - 1);
        
        if (i != 0) {
            if (a.at(i) - a.at(i - 1) == 1) {
                answer += c.at(a.at(i - 1) - 1);
            }
        }
    }
    
    
    cout << answer << endl;
    }


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include<limits.h>
#include<stdio.h>
#include<cstring>
#include<string>
using namespace  std;
typedef long long ll;
typedef long double ld;
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
#define mp make_pair
#define sz(a) a.size()
#define fi first
#define se second
#define rsz(a,n) a.resize(n)
#define test(t) ll t;cin>>t;while(t--)
#define forn(i,e) for(int i = 0; i < e; i++)
#define forsn(i,s,e) for(int i = s; i < e; i++)
#define rforn(i,s) for(int i = s; i >= 0; i--)
#define rforsn(i,s,e) for(int i = s; i >= e; i--)
#define fillv(a,k) memset(a,k,sizeof(a))
#define leadzero(a) __builtin_clz(a) //count leading zeros
#define trailzero(a) __builtin_ctz(a) //count trailing zeros
#define bitcount(a) __builtin_popcount(a) // count set bits (add ll)
#define ln cout<<"\n"
// #define sp cout<<" "
#define spaceprint(a,i,s,n) {forsn(i,s,n) { cout<<a[i]; sp;}}
#define lineprint(a,i,s,n) {forsn(i,s,n) {cout<<a[i]; ln;}}
#define maxe(a) *max_element(a.begin(),a.end())
#define maxi(a) max_element(a.begin(),a.end())-a.begin()
#define mine(a) *min_element(a.begin(),a.end())
#define mini(a) min_element(a.begin(),a.end())-a.begin()
#define all(c) c.begin(),c.end()
#define trav(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define present(container, element) (container.find(element) != container.end())
#define cpresent(container, element)  (find(all(container),element) != container.end())// check the presence of element
//copy(from_begin, from_end, to_begin); copy function
typedef unsigned long long int ull;
typedef long double ld;
typedef pair<ll,ll> p64;
typedef pair<int,int> p32;
typedef pair<int,p32> p96;
typedef vector<ll> v64;
typedef vector<string> vs;
typedef vector<int> v32;
typedef vector<v32> vv32;
typedef vector<v64> vv64;
typedef vector<p32> vp32;
typedef vector<p64> vp64;
typedef vector<vp32> vvp32;
typedef map<int,int> m32;
typedef map<ll,ll> m64;
const int LIM = 1e5+5, MOD =  1e9;
#define sumv(v) accumulate(all(v),ll(0))
#define productv(v) accumulate(all(v), ll(1), multiplies< ll >())
ll gcd(ll a, ll b) { if(b == 0) return a; return gcd(b, a % b); }
ll fastpowMOD(ll a, ll p,ll MOD){ if(p==0) return 1; ll z = fastpowMOD(a,p/2,MOD); z = (z*z)%MOD; if(p%2) z = (z*a)%MOD; return z; }
bool seive[100005];
void SieveOfEratosthenes(ll n)
{ memset(seive, true, sizeof(seive)); for (ll p=2; p*p<=n; p++) if (seive[p] == true) for (ll i=p*p; i<=n; i += p) seive[i] = false; }
// ll a[11*LIM]={0},b[11*LIM]={0};
// vp64 v[LIM];
typedef struct 
{
	ll one,two,three;
}data;






int main()
{
	fast;
	ll n,k;
	cin>>n>>k;
	n=n%k;
	cout<<min(n,k-n);
}

Measured memory_bytes: 256
n = int(input())
d = {}
sum = 0

for i in range(n):
  s = list(input())
  s.sort()
  t = "".join(s)
  s.clear()
  if t in d:
    d[t] += 1
  else:
    d[t] = 1
    
for i in d:
  if d[i] > 1:
    sum += (d[i]*(d[i]-1))/2

print(int(sum))


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

#define ll long long int
#define pb push_back

int main(){
    ios_base::sync_with_stdio(false);
    ll n;
    cin>>n;
    double p[n];
    for(ll i=0; i<n; i++){
        cin>>p[i];
    }
    double dp[n+1][n+1];
    dp[1][0] = 1-p[0];
    dp[1][1] = p[0];
    for(ll i=2; i<=n; i++){
        for(ll j=0; j<=i; j++){
            dp[i][j] = ((j==0) ? 0 : dp[i-1][j-1]*p[i-1]) + ((j==i) ? 0 : dp[i-1][j]*(1-p[i-1]));
            // cout<<i<<" "<<j<<" "<<": "<<dp[i][j]<<endl;
        }
    }
    double ans = 0;
    for(ll i=n/2 + 1; i<=n; i++){
        ans+=dp[n][i];
    }
    cout<<setprecision(9);
    cout<<ans<<"\n";
}

Measured memory_bytes: 70528
#include <iostream>

int main(int argc, char **argv)
{
    int N;
    std::cin >> N;

    long sum = 0;
    for(int i = 1; i <= N; i++){
        if(i % 3 == 0 || i % 5 == 0){
            // pass
        }else{
            sum += i;
        }
    }
    std::cout << sum << std::endl;
}


Measured memory_bytes: 3628
#include <iostream>
#include <vector>

using namespace std;

int main(){
    // input
    int n, m, l;
    cin >> n >> m >> l;

    vector <vector <int> > a(n, vector<int>(m));
    for (int i=0; i<n; i++){
        for  (int j=0; j<m; j++){
            cin >> a.at(i).at(j);
        }
    }
    vector <vector <int> > b(m, vector<int>(l));
    for(int i=0; i<m; i++){
        for  (int j=0; j<l; j++){
            cin >> b.at(i).at(j);
        }
    }

    // calucuration
    vector <vector <long int> > c(n, vector<long int>(l));
    for (int i=0; i<n; i++){
        for  (int j=0; j<m; j++){
            for(int k=0; k<l; k++){
                c.at(i).at(k) += a.at(i).at(j) * b.at(j).at(k);
            }
        }
    }

    // output
    for(int i=0; i<n; i++){
        for(int j=0; j<l; j++){
            cout << c.at(i).at(j);
            if(j != l-1) cout << " ";
        }
        cout << endl;
    }

    return 0;
}



Measured memory_bytes: 3236
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define scanVec(vec , n) for(int i = 0; i < n ; i++){ cin>>vec[i];} 
#define printVec(vec , n) for(int i = 0; i < n ; i++){ cout<<vec[i]<<" ";} cout<<endl;
#define S second
#define F first
#define SZ(x) (int)x.size()
typedef long long ll;
const int  MOD = 1e9 + 7;
const int  N = 1e6 + 7;
int res[N];

void solve(){
    int n , m , p; 
    cin>>n>>m;
    string s;
    int ac = 0 , pen = 0;
    for(int i = 0 ; i < m ; i++){
        cin>>p>>s;
        if(res[p] > 0) continue;
        if(s == "AC"){
            ac++;
            pen -= res[p];
            res[p] = 1;
        }else{
            res[p]--;
        }
    }
    cout<<ac<<" "<<pen<<endl;
}

int main(){
    ios::sync_with_stdio(0);  cin.tie(0); cout.tie(0);
    int t = 1;
    // cin>>t;
    while(t--) solve();
    return 0;
}

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

#define MOD 1000000007

using namespace std;

typedef long long int ll;

int n;
int a[25][25];
int dp[22][(1 << 21) + 500];

void add_self(int &a, int b) { a += b; if (a >= MOD) a -= MOD; }
void sub_self(int &a, int b) { a -= b; if (a < 0) a += MOD; }

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

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			scanf("%d", &a[i][j]);

	dp[0][0] = 1;

	for (int i = 1; i <= n; i++) {

		for (int mask = 0; mask < (1 << n); mask++) {

			if (dp[i - 1][mask] == 0) continue;

			for (int j = 0; j < n; j++)
				if (a[i][j + 1] == 1 && ((mask >> j) & 1) == 0) {

					add_self(dp[i][mask + (1 << j)], dp[i - 1][mask]);
				}
		}
	}

	printf("%d", dp[n][(1 << n) - 1]);

	return 0;
}

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


int main(){
    
    int a, b;
    
    cin >> a >> b;
    
    for(int i = 1;i < 999;++i){
        if(i * (i + 1) / 2 - a == (i + 1) * (i + 2) / 2 - b && i * (i + 1) / 2 - a > 0){
            cout << i * (i + 1) / 2 - a << endl;
            break;
        }
    }
    
    return 0;
}

Measured memory_bytes: 256
require 'set'
n, k = gets.strip.split.map(&:to_i)
td = readlines.map {|line| line.strip.split.map(&:to_i) }

td = td.sort_by {|td| td.last*-1 }

selected = td[0, k]
unselected = td[k, n]

current_kinds = Set.new(selected.map(&:first))
current_score = selected.map(&:last).inject(:+)
max = current_score + current_kinds.size**2

if n==k
  p max
  exit
end

dup_set = Set.new
dups_in_selected = []
selected.each do |t, d|
  if dup_set.include?(t)
    dups_in_selected << [t,d]
  else
    dup_set << t
  end
end

unselected.each do |t, d|
  next if current_kinds.include?(t)
  removed = dups_in_selected.pop
  break if removed.nil?
  current_score -= removed.last
  current_score += d
  current_kinds << t
  tmp_max = current_score + current_kinds.size**2
  max = tmp_max if tmp_max > max
end

p max




grouped_td = td.group_by(&:first)

sushi_max = grouped_td.map {|t, arr| [t, arr.map(&:last)] }.map {|t, arr| [t, arr.sort.reverse] }



Measured memory_bytes: 53072
n = gets.to_i
s = gets.chomp
tmp = 0
cum = [0]
min = 3 * 10**5 - 1

s.each_char do |c|
  tmp += 1 if c == 'W'
  cum << tmp
end

1.upto(n) do |i|
  tmp = cum[i - 1] + n - i - (cum[-1] - cum[i])
  min = tmp if min > tmp
end

puts min

Measured memory_bytes: 6916
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
#
# インデックス系
# int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
# int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
#
#
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
#mod = 998244353
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
  return int(readline())
x,y = readInts()
cnt = 1
while x <= y:
    x += x
    if x <= y:
        cnt += 1
print(cnt)


Measured memory_bytes: 10312
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define pb push_back
#define mp make_pair
#define in insert
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define mod 1e9+7
#define sz(v) (int)(v.size())
#define all(x) x.begin(), x.end()
#define prec fixed << setprecision(12)
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define test int t; cin >> t; while(t--)
#define inf 1e9+5

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef set<int> si;
typedef map<int, int> mii;
typedef vector<pii> vpi;

void solve() {
	int n, k;
	cin >> n >> k;
	vi h(n);
	rep(i, 0, n - 1) cin >> h[i];
	vi dp(n, inf);
	dp[0] = 0;
	rep(i, 0, n - 1) {
		for (int j = i + 1; j <= i + k; j++) {
			if (j < n) {
				dp[j] = min(dp[j], dp[i] + abs(h[i] - h[j]));
			}
		}
	}
	cout << dp[n - 1];
}

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

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	// test
	solve();


	return 0;
}

Measured memory_bytes: 4780
n=int(input())
h=list(map(int, input().split()))
max=h[0]

for i in range(n):
    if h[i]>max:
        max=h[i]
    if h[i]<max-1:
        print("No")
        break
    if i==n-1:
        print("Yes")
        break

Measured memory_bytes: 14252
#include<stdio.h>

int main()
{
	int tc, num[100000], count=0, i, save, acd[100000];

	scanf("%d", &tc);

	for(i = 1; i<= tc; i++)
	{
		scanf("%d", &num[i]);
		acd[i] = i;
	}
	for(i = 1; i <= tc; i++)
	{
		if(acd[i] == num[i])
            save = 1;
        else
            count++;
	}
    if(count <= 2 && save == 1)
        printf("YES\n");
    else
        printf("NO\n");


	return 0;
}

Measured memory_bytes: 1608
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <queue>
#include <unordered_map>
#include <set>
#include <algorithm>
#include <utility>
#include <cmath>
using namespace std;

typedef long long llong;
typedef unsigned long long ullong;
// -2.1e-9 <= int <= 2.1e9
// -9.2e-18 <= long long <= 9.2e18
// 0 <= unsigned int <= 4.2e9
// 0 <= unsigned long long <= 18.4e18
// cout << fixed << setprecision(10);

int main() {
    uint N, M;
    llong K;
    cin >> N >> M >> K;

    vector<int> A(N, 0);
    vector<int> B(M, 0);
    for (auto &a: A) cin >> a;
    for (auto &b: B) cin >> b;

    vector<llong> sumA(N+1, 0);
    vector<llong> sumB(M+1, 0);
    for (uint i=1; i<sumA.size(); i++)
        sumA[i] = sumA[i-1] + A[i-1];
    for (uint i=1; i<sumB.size(); i++)
        sumB[i] = sumB[i-1] + B[i-1];

    auto pos = lower_bound(sumA.begin(), sumA.end(), K);
    uint numAmax = 0;
    int d = 0;
    if (pos == sumA.end())
        d = sumA.size() - 1;
    else if (*pos > K)
        d = distance(sumA.begin(), pos) - 1;
    else
        d = distance(sumA.begin(), pos);

    if (d < 0) numAmax = 0;
    else numAmax = d;

    vector<uint> numRead(N+1, 0);
    uint numReadMax = 0;
    // Aの机からnumA冊読んだ場合Bの机から何冊読めるか
    for (uint numA=0; numA<=numAmax; numA++) {

        ullong K2 = K - sumA[numA];
        auto pos = lower_bound(sumB.begin(), sumB.end(), K2);
        int d = 0;
        uint numB;
        if (pos == sumB.end())
            d = sumB.size() - 1;
        else if (*pos > K2)
            d = distance(sumB.begin(), pos) - 1;
        else
            d = distance(sumB.begin(), pos);
        if (d < 0) numB = 0;
        else numB = d;

        numRead[numA] = numA + numB;
        if (numRead[numA] > numReadMax)
            numReadMax = numRead[numA];
    }
    cout << numReadMax << endl;
    return 0;
}



Measured memory_bytes: 8796
#include <iostream>
#include <vector>
#include <iomanip>
#include <stack>
#include <array>
#include <deque>
#include <forward_list>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iterator>
#include <string>
#include <cstring>
#include <fstream>
#include <random>
#include <time.h>
#include <complex>
#include <cmath>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=n;i>0;i--)
#define arep(a,i,n) for(int i=(a);i<(n);i++)
#define SORT(v) sort((v).begin(),(v).end())
#define TEMP(type,x,y) do {temp temp=x,x=y,y=temp}while(0)
const ll INF = (1LL << 50);
typedef pair<ll, ll> P;

bool cmp(const P &a, const P &b) {
	return a.first + a.second > b.first + b.second;
}

int main() {

	int n;
	cin >> n;
	
	vector<P> dish(n);

	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		dish.push_back(make_pair(a, b));
	}

	sort(dish.begin(), dish.end(), cmp);

	ll score = 0;
	for (int i = 0; i < n; i++) {
		if (i%2 == 0) {
			score += dish[i].first;
		}
		else {
			score -= dish[i].second;
		}
	}

	cout << score << endl;

	return 0;

}

Measured memory_bytes: 4480
#include<stdio.h>
int main ()
{
    int A,B;
    int C,D;
    scanf("%d %d",&A,&B);
    scanf("%d %d",&C,&D);


    if(A>=B && C>=D)
    {
        printf("%d\n",B+D);
    }
    else if(A>=B && D>=C)
    {
        printf("%d\n",B+C);
    }
    else if(B>=A && C>=D)
    {
        printf("%d\n",A+D);
    }
    else
    {
        printf("%d\n",A+C);
    }

    return 0;
}


Measured memory_bytes: 128
//-----Rashish-----//
#include<bits/stdc++.h>
typedef long long ll;

using namespace std;

#define REP(i,a,b) for (int i = a; i <= b; i++)
#define endl '\n'
#define ALL(a)              a.begin(), a.end()
#define ALLN(a, n)          (a, a+n)
#define MAX                 10000007
#define MIN                 -10000007
#define ff              first
#define ss              second
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
#define pw(b,p)         pow(b,p) + 0.1
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());

ll hcf(ll n1, ll n2) {if (n2 != 0)return hcf(n2, n1 % n2); else return n1;}
ll fact(ll n) { ll i = 1, co = 1; for (i = 1; i <= n; i++)co *= i; return co;}
ll isprime(ll n) {
    if (n <= 1) return 0; if (n <= 3) return 1; if (n % 2 == 0 || n % 3 == 0) return 0;
    for (ll i = 5; i <= sqrt(n); i += 6) { if (n % i == 0 || n % (i + 2) == 0) return 0; } return 1;
}
ll sod(ll n) {ll sum = 0; while (n) {sum += n % 10; n /= 10;} return sum;}




int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
#endif

    int t;
    t = 1;
    //cin>>t;
    while (t--) {
        ll n;
        cin >> n;
        ll q = 0;
        q = n % 1000;
        if (q > 0) {
            q = 1000 - q;
        }
        cout << q << endl;



    }

    return 0;
}


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

int main() {
  int N;
  cin >> N;
  vector<int> a(N);
  for(int i=0; i<N; i++){
    cin >> a[i] ;
  }
  sort(a.begin(), a.end());
  int i=0 , ans = 1;
    for(int j=i; j<N; j++){
      if(a[i] != a[j]){
        ans ++;
        i = j;
      }
    }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdio>

using namespace std ;

#define pb(n) push_back(n)
#define fi first
#define se second
#define all(r) (r).begin(),(r).end()

#define rep(i,n) for(int i = 0; i < (n);++i)
#define repc(i,a,b) for(int i = (a);i <(b);++i)
#define repa(n,array) for(auto n :(array))

typedef long long ll ;
typedef vector<int> vi ;
typedef vector<ll> vl ;

constexpr int IMAX = ((1<<30)-1)*2+1 ;
constexpr int INF = 100000000;
double EPS = 1e-10 ;

int main(){
  int hit,blow,w,x,y,z;
  vi a(4,0),b(4,0) ;
  while(cin >> w >> x >> y >> z){
    hit = 0,blow = 0;
    a[0] = w,a[1] = x,a[2] = y,a[3] = z ;
    for(int i =0; i < 4; ++i){
      cin >> x ;
      b[i] = x ;
    }
    rep(i,4){
      rep(j,4){
        if(a[i] == b[j] && i == j){
          ++hit ;
        }
        else if(a[i] == b[j]){
          ++blow ;
        }
      }
    }
    cout << hit << " " << blow << endl ;
  }
  return 0;
}

Measured memory_bytes: 1192