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

using namespace std; 

int main()
{
	int n ; 
	cin>>n ; 
	vector<double> dp(n+1);
	dp[0]=1;
	for( int i=0 ; i<n ; i++ )
	{
		double p;
		scanf("%lf",&p);
		// cin>>p;
		for( int j=i+1 ; j>=0; j-- )
			dp[j] = (j==0 ? 0 : dp[j-1]*p) + dp[j]*(1-p) ;
		
	}

	double ans = 0 ; 
	for( int i=0 ; i<=n ; i++ )
	{
		int tails = n-i;
		if( i > tails )
			ans +=	dp[i];
	}
	
	printf("%.10lf\n", ans);
	// cout<<ans<<endl;

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main() {
	int k;
	while (cin >> k) {
		if (!k)return 0;
		int sum = 0;
		for (int i = 0; i < k*(k - 1) / 2; i++) {
			int a; cin >> a;
			sum += a;
		}
		cout << sum / (k - 1) << endl;
	}
}

Measured memory_bytes: 3012
from heapq import heapify, heappush, heappop
from collections import deque
from copy import deepcopy, copy
N = 3
def g(i, j, a):
    if i > j:
        i, j = j, i
    return a[:i] + a[j] + a[i + 1:j] + a[i] + a[j + 1:]
def MAIN():
    m = {8:{7, 5}, 7:{8, 6, 4}, 6:{7, 3}, 5:{8, 4, 2}, 4:{7, 5, 3, 1}, 3:{6, 4, 0}, 2:{5, 1}, 1:{4, 2, 0}, 0:{3, 1}}
    MAP = "".join(input().replace(" ", "") for _ in range(N))
    start = MAP.find("0")
    goal = "123456780"
    dp = [(0, MAP, start)]
    LOG = {MAP}
    while dp:
        cnt, M, yx = heappop(dp)
        if M == goal:
            print(cnt)
            break
        cnt += 1
        for nyx in m[yx]:
            CM = g(yx, nyx, M)
            if not CM in LOG:
                heappush(dp, (cnt, CM, nyx))
                LOG.add(CM)
MAIN()



Measured memory_bytes: 31360
#include<stdio.h>
int main(void)
{
	char a[101][101];
	int x,y;
	scanf("%d%d",&x,&y);
	int i,j;
	getchar();
	for(i=0;i<x;i++)
	{
		for(j=0;j<y;j++)
		   scanf("%c",&a[i][j]);
		getchar();    
	}
	/*for(i=0;i<x;i++)
	{
		for(j=0;j<y;j++)
		   printf("%c",a[i][j]);
		printf("\n");
	}*/
	for(i=x;i>=1;i--)
		for(j=y;j>=1;j--)
		   a[i][j]=a[i-1][j-1];
	for(i=0;i<=x+1;i++)
	{
	    for(j=0;j<=y+1;j++)
		{
			if(i==0||i==x+1||j==0||j==y+1) 
			   printf("#");
            else printf("%c",a[i][j]); 			
		}	
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    int d[n],x,y,i;
    d[0]=0;
    d[1]=abs(a[1]-a[0]);
    for(i=2;i<n;i++)
    {
        x=d[i-1]+abs(a[i]-a[i-1]);
        y=d[i-2]+abs(a[i]-a[i-2]);
        d[i]=min(x,y);
    }
    cout<<d[i-1];
}


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

#ifdef _DEBUG
inline void dump() { cerr << endl; }
template<typename Head> void dump(Head&& head) { cerr << head; dump(); }
template<typename Head, typename... Tail> void dump(Head&& head, Tail&&... tail) { cerr << head << ", "; dump(forward<Tail>(tail)...); }
#define debug(...) do {cerr << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; dump(__VA_ARGS__); } while (false)
#else
#define dump(...)
#define debug(...)
#endif

template<typename T>
struct edge {
  int src, to;
  T cost;
  edge(int to, T cost) : src(-1), to(to), cost(cost) {}
  edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}
  edge &operator=(const int &x) {
    to = x;
    return *this;
  }
  operator int() const { return to; }
};
template<typename T>
using Edges = vector<edge<T>>;
template<typename T>
using WeightedGraph = vector<Edges<T>>;
using UnWeightedGraph = vector<vector<int>>;
template<typename T>
using Matrix = vector<vector<T>>;

/////////////////////////////////////////////////////////////////////

const ll inf = 1LL<<60;

int main()
{
  ll n; cin >> n;
  vector<ll> a(n);
  for (int i=0; i<n; i++){
    cin >> a[i];
  }
  a.push_back(1);

  ll m = 1000;
  ll l = 0;
  ll mmax = m;

  for (int i=0; i<=n; i++) {
    if (l == 0) {
      if (a[i] < a[i+1]) {
        l = m/a[i];
        m -= a[i]*l;
      }
    } else {
      if (a[i] > a[i+1]) {
        m += a[i]*l;
        l = 0;
      }
    }
    mmax = max(mmax, m);
  }
  cout << mmax << endl;

  return 0;
}


Measured memory_bytes: 3588
using System;

class D {
    static string Solve(string s) {
        for (int i = 1; i < s.Length; ++i)
            if (s[i] == s[i - 1]) return $"{i} {i + 1}";
        for (int i = 2; i < s.Length; ++i)
            if (s[i] == s[i - 2]) return $"{i - 1} {i + 1}";
        return "-1 -1";
    }

    public static void Main() {
        var s = Console.ReadLine();
        Console.WriteLine(Solve(s));
    }
}


Measured memory_bytes: 13280
#include<bits/stdc++.h>
using namespace std;
#define vi vector<int> 
#define vll vector<ll> 
#define vpll vector<pair<ll ,ll>>
#define vvi vector<vector<int>>
#define vvll vector<vector<ll>>
#define map map<ll ,ll>
#define umap unordered_map<ll , ll>
#define endl "\n"
#define set set<ll> 
#define setC set<char>
#define all(x) x.begin() , x.end()
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define fastcout ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define testcases int tt = 1 ; cin >> tt ; for(int i = 1 ; i <= tt ; ++i)
#define codejam cout << "Case #"<<i <<": "; 
#define FOR(i,a,n) for(int i = a ; i <= n ; ++i)
#define FORback(i,a,n) for(int i = n ; i >= a ; --i)
#define ll long long int
const ll INF = 1e13+7;
const ll mod = 1e9+7;


// vector<vvi> dp;
vector<vector<vector<double>>> dp;

double doSome(int a , int b , int c , int n){


    if( a < 0 or b < 0  or c < 0 ){
        return 0;
    }
    else if(a == 0  and b == 0  and c == 0){
        return dp[a][b][c] = 0 ; 
    }

    if(dp[a][b][c] > -1){
        return dp[a][b][c];
    }

    double first_sushi = a * doSome(a-1 , b , c , n );
    double second_sushi = b * doSome(a+1 , b-1 , c , n );
    double third_sushi = c * doSome(a , b+1 , c-1 , n);

    return dp[a][b][c] = (n + first_sushi +second_sushi +third_sushi) / (a+b+c);
}

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

    vi arr(n);

    FOR(i , 0 , n-1){
        cin >>arr[i];
    }

    dp.assign(n+1 , vector<vector<double>>(n+1 , vector<double>(n+1 , -1)));

    map mp;
    
    for(auto x : arr){
        mp[x]++;
    }

    cout << setprecision(20) << doSome(mp[1] , mp[2] , mp[3] , n ) << endl;

}

int main(){
    fast ;    
    // testcases{
        // codejam ;
        solv();
    // } 
}




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

struct task {
	char name[11];
	int time;
};
const int MAX = 100000;
int front = 0, rear = 0;
task T[MAX];

int n, q;
void Enqueue(task t[], task x)
{
	rear = (rear + 1) % MAX;
	t[rear] = x;
}


void Dequeue(task t[], task &x)
{
	front = (front + 1) % MAX;
	x = t[front];
}

int main()
{
	cin >> n >> q;
	for (int i = 0; i < n; ++i)
	{
		task t;
		scanf("%s %d", t.name, &t.time);
		Enqueue(T, t);
	}

	/*******/
	task t;
	int cnt = 0;
	int tt;
	while (rear != front)
	{
		Dequeue(T, t);
		tt = min(q, t.time);
		t.time -= tt;
		cnt += tt;
		if (t.time > 0) Enqueue(T, t);
		else printf("%s %d\n", t.name, cnt);
	}
	/*************/
	///****************************//
	//int sum = 0;
	//for (int i = 1; i <= n; ++i)
	//	sum += T[i].time;
	//
	//int cnt = q;
	//task t;
	//Dequeue(T, t);
	//for (int i = 0; i < sum; ++i)
	//{
	//	
	//	t.time--;
	//	cnt--;
	//	if (t.time == 0) {
	//		printf("%s %d\n", t.name, i + 1);
	//		if (rear == front) break;
	//		Dequeue(T, t);
	//		cnt = q;
	//	}
	//	else if (cnt == 0) {
	//		Enqueue(T, t);
	//		Dequeue(T, t);
	//		cnt = q;
	//		
	//	}
	//	
	//}
	///////////////////////////////////

	return 0;
}


Measured memory_bytes: 4712
#include<cstdio>
#include<cctype>

int main() {
	char c[1201];
	int i = 0;

	while (true) {
		scanf("%c",&c[i]);
		if (c[i] == '\n') break;
		i++;
	}
	i = 0;
	
	while (true) {
		if (islower(c[i]))	printf("%c", toupper(c[i]));
		else if (isupper(c[i])) printf("%c",tolower(c[i]));
		else printf("%c",c[i]);
		
		if (c[i] == '\n') break;
		i++;
	}

	return 0;
}

Measured memory_bytes: 944
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define PI 3.14159265358979323846
#define int long long
constexpr long long INF = numeric_limits<long long>::max() / 2;
constexpr int MOD = 1000000007;
using Graph = vector<vector<int>>;



signed main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int H,W;
    cin>>H>>W;
    int c[10][10];
    rep(i,10){
        rep(j,10){
            cin>>c[i][j];
        }
    }
    int A[H][W];
    rep(i,H){
        rep(j,W){
            cin>>A[i][j];
        }
    }

    for(int k=0;k<10;k++){
        for(int i=0;i<10;i++){
            for(int j=0;j<10;j++)c[i][j]=min(c[i][j],c[i][k]+c[k][j]);
        }
    }
    int ans=0;
    rep(i,H){
        rep(j,W){
            if(A[i][j]!=-1) ans+=c[A[i][j]][1];
        }
    }
    cout << ans << endl;

    



}


Measured memory_bytes: 640
#include<bits/stdc++.h>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<iostream>
#define ios   ios_base::sync_with_stdio(false);  cin.tie(0);    cout.tie(0);
typedef long long int ll;
typedef long double ld;
using namespace std;
const int M=1e9+7;
#include<iostream> 
#include<climits> 
using namespace std; 
int main() {
    ios;
   ll h,a;cin>>h>>a;
   if(h%a==0)
   cout<<h/a;
   else
   cout<<h/a+1;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define SZ(X) ((int)(X).size())
#define endl "\n";
typedef long long ll;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
	int n;
		cin>>n;
	 ll ans=0;
	for (int i = 1; i <= n; ++i)
		{
			if(i%3!=0&&i%5!=0){
				ans+=i;	
			}
			
		}	
    cout<<ans;
   return 0;
}


Measured memory_bytes: 3588
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cstdlib>
#define LL long long
#define LD long double
using namespace std;
const int NN=5000 +117;
const int MM=5000 +117;
int read(){
	int fl=1,x;char c;
	for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
	if(c=='-'){fl=-1;c=getchar();}
	for(x=0;c>='0'&&c<='9';c=getchar())
		x=(x<<3)+(x<<1)+c-'0';
	return x*fl;
}
void open(){
	freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
}
void close(){
	fclose(stdin);
	fclose(stdout);
}


int n,k;
char s[2*NN]={};
char a[NN]={};
void upd(char a[],char b[]){
	for(int i=0;i<n;++i){
		if(a[i]!=b[i]){
			if(a[i]<b[i])return;
			else{
				for(int i=0;i<n;++i){
					a[i]=b[i];
				}
				return ;
			}
		}
	}
}
int main(){
	//open();
	n=read();
	k=read();
	scanf("%s",s+1);
	for(int i=0;i<n;++i)a[i]=s[i+1];
	for(int i=n+1;i<=2*n;++i)s[i]=s[2*n+1-i];
	for(int i=1;i<=n+1;++i){
		upd(a,s+i);
	}
	int cnt=0;
	int pos=0;
	for(pos=0;pos<n;++pos){
		if(a[pos]!=a[0])break;
		else ++cnt;
	}
	for(int i=2;i<=k;++i){
		cnt*=2;
		if(cnt>=n)break;
	}
	if(cnt>=n)cnt=n;
	for(int i=1;i<=cnt;++i){
		putchar(a[0]);
	}
	for(int i=cnt+1;i<=n;++i){
		putchar(a[pos++]);
	}
	putchar('\n');
	close();
	return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define _ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define    common(a,b)      SORT(a), SORT(b), a.erase(set_intersection(all(a),all(b),a.begin()),a.end())
#define    uncommon(a,b)    SORT(a), SORT(b), a.erase(set_symmetric_difference(all(a),all(b),a.begin()),a.end())
#define    minv(v)         *min_element(all(v))
#define    maxv(v)         *max_element(all(v))
#define    SORT(v)          sort(all(v))
#define    REV(x)           reverse(x.begin(),x.end())
#define    all(x)           x.begin(), x.end()
#define    rev(v)           reverse(all(v))
#define    unq(v)           sort(all(v)),v.erase(unique(all(v)),v.end())
#define    fr(i,x,n)        for(int i=x;i<n;i++)
#define    trav(a,x)        for (auto &a: x)
#define    sz(x)            (ll)(x).size()
#define    ll               long long int
#define    pb               push_back
#define    in               insert
#define    gcd(a, b)        __gcd(a, b)
#define    lcm(a, b)        ((a)*((b)/gcd(a,b)))
#define    w(t)              cin>>t;while(t--)
const ll mod = 1000000007;
const double pi = acos(-1.0);
/*bool isprime(int x)
{
    if(x==0 or x==1)return false;
    for(int i=2; i*i<=x; i++)
    {
        if(x%i==0)
            return false;
    }
    return true;
}*/
/*ll power(ll n,ll b,ll mod)
{
    ll res=1;
    while(b)
    {
        if(b%2)res=((n%mod)*(res%mod))%mod,b--;
        else n=((n%mod)*(n%mod))%mod,b/=2;
    }
    return res;
}*/
string str[]= {"YES","NO"};
int main()
{
    _ios
    ll z;
    //w(z)
    //{
        ll n,m,a,b,c,d,e,x,y,mul=1,cn=0,cn1=0,cn2=0,sm=0,sm1=0,sm2=0,mx=INT_MIN,mx1=INT_MIN,mn=INT_MAX,mn1=INT_MAX,i,j,k,temp;
        string s,ss,st1,st2;
        char ch;
        set<ll>st;
        map<char,ll>mp,mp1;
        bool f=true,ff=true;
        cin>>a>>b>>c;
        cout<<(b*c>=a?"Yes":"No")<<endl;
        /*if(a%2==0 and sqrt(a)*sqrt(a)!=a)
           cout<<min(a%2,a/2)<<endl;
          else
              cout<<max(a%2,a/2+1)<<endl;*/
    //}
    return 0;
}


Measured memory_bytes: 3648
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<iomanip>
#define rep(i,n)for(int i=0;i<n;i++)
using namespace std;
signed main(){
	int x, y;
	cin >> x >> y;
	if (x%y==0)cout << -1 << endl;
	else cout << x << endl;
	getchar(); getchar(); return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <vector>
#include <queue>
#include <functional>
#include <algorithm>
#include <cmath>
#include <string>
#include <set>
#include <cstdio>
#define mp make_pair
#define pb push_back

using namespace std;

int main() 
{
	int a, b;
	cin >> a >> b;
	if (a >= 2*b - 1) {
		cout << "YES\n";
	}
	else
		cout << "NO\n";
	return 0;
}

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

int n;
vector<int> G[105];
int ms[105];

int dfs(int v, int par, int dep)
{
	int ret = 0;
	ms[dep] = max(ms[dep], int(G[v].size()) - (par >= 1 ? 1 : 0));
	rep(i, G[v].size()) {
		int u = G[v][i];
		if(u == par) continue;
		ret = max(ret, dfs(u, v, dep + 1));
	}
	return ret + 1;
}

pair<LL, LL> solve_tp1(int v)
{
	rep(i, n) ms[i] = 1LL;
	int md = dfs(v, -1, 0);
	pair<LL, LL> cur = MP(md, 1LL);
	rep(i, md) cur.second *= ms[i];
	return cur;
}

pair<LL, LL> solve_tp2(int u, int v)
{
	rep(i, n) ms[i] = 1LL;
	int md = max(dfs(v, u, 0), dfs(u, v, 0));
	pair<LL, LL> cur = MP(md, 2LL);
	rep(i, md) cur.second *= ms[i];
	return cur;
}

int main()
{
	scanf("%d", &n);
	rep(i, n - 1) {
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	pair<LL, LL> ans = MP(INF, -1);
	rep1(i, n) ans = min(ans, solve_tp1(i));
	rep1(i, n) rep(j, G[i].size()) ans = min(ans, solve_tp2(i, G[i][j]));
	printf("%lld %lld\n", ans.first, ans.second); 
	return 0;
}

Measured memory_bytes: 256
function main(input) {
  let [n, m, q] = input[0].trim().split(" ").map(i => parseInt(i));

  let [a,b,c,d] = [[],[],[],[]];
  for(i=0;i<q;i++){
    [a[i], b[i], c[i], d[i]] = input[i+1].trim().split(" ").map(i => parseInt(i));
  }

  let A = [];

  /*　再帰頑張った　*/
  function recursive(current) {
    if(current.length>=n){
      A.push(current)
      return;
    }
    for(let i=1;i<=m;i++){
      if(current.length===0){
        recursive([i]);
      }else if((current[current.length-1]<=i)){
        recursive([...current,i]);
      }
    }
  }

  recursive([]);
  
  let max=0;
  for(let value of A){
    let sum=0;
    for(let i=0;i<q;i++){
      if(value[b[i]-1]-value[a[i]-1]===c[i]){
        sum+=d[i];
      }
    }
    if(max<sum){
      max = sum;
    }
  }
  console.log(max);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8').trim().split("\n"));

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

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

  int sum = 0;
  int b = n;
  for (int i = 0; i < 8; ++i) {
    sum += b % 10;
    b /= 10;
  }

  if (n % sum == 0) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
N = int(input())
S = input()
'''
Editorialのヒントを参照しました。
000 ~ 999の実現可能性を考えます。
'''
L = []
s = ''
Comb = 0
key_k = False
for i in range(0, 10):
    for j in range(0, 10):
        if key_k is not True:
            s += str(j)
        else:
            s += str(i)
            s += str(j)
            key_k = False
        for k in range(0, 10):
            s += str(k)
            L.append(s)
            s = ''
            s += str(i)
            s += str(j)
        s = ''
        key_k = True
L.remove(L[0])
L.append('000') #生成、もう少し短くしたい
S_copy = S
A = []
for el in L:
    c0 = el[0]
    c1 = el[1]
    c2 = el[2]
    S = S_copy
    N0 = S.find(c0)
    if N0 == -1:
        continue
    else:
        S = S[N0+1::]
        N1 = S.find(c1)
        if N1 == -1:
            continue
        else:
            S = S[N1+1::]
            N2 = S.find(c2)
            if N2 == -1:
                continue
            else:
                Comb += 1
print(Comb)

Measured memory_bytes: 9384
N, M = [int(x) for x in input().split()]
L = list()
R = list()
for i in range(M):
  l, r = [float(x) for x in input().split()]
  L.append(l)
  R.append(r)
Lmax = max(L)
Rmin = min(R)
if(Rmin-Lmax)<0:
  print(0)
else:
  print(int(Rmin-Lmax+1))

Measured memory_bytes: 16972
import sys
def side(p1, p2, p3): return (p3[1]-p1[1])*(p2[0]-p1[0])-(p2[1]-p1[1])*(p3[0]-p1[0])>0
 
for s in sys.stdin:
  x = map(float, s.split())
  p1 = x[0:2]
  p2 = x[2:4]
  p3 = x[4:6]
  p0 = x[6:]
  print ["NO","YES"][(side(p1, p2, p0)==side(p2, p3, p0) and side(p2, p3, p0)==side(p3, p1, p0))]

Measured memory_bytes: 4244
#include <bits/stdc++.h>
#define ll long long 
#define ff first
#define ss second
#define mp make_pair
#define fastio() ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
using namespace std;
int main() {
	fastio();
	int n,i;
	cin>>n;
	int h[n];
	for(i=0;i<n;i++)
	{
		cin>>h[i];
	}

	int dp[n];
	dp[0]=0;
	dp[1]=abs(h[1]-h[0]);

	for(i=2;i<n;i++)
	{
		dp[i]= min ( dp[i-1]+abs(h[i]-h[i-1]),
					 dp[i-2]+abs(h[i]-h[i-2])  );
	}
	cout<<dp[n-1];
	return 0;
}




Measured memory_bytes: 1024
import sys


def input(): return sys.stdin.readline().strip()


def solve():
    pass


def main():
    N = int(input())
    H = list(map(int, input().split()))

    ans = 0
    c = 0

    for i in range(N-1):
        if H[i] >= H[i+1]:
            c += 1
        else:
            c = 0
        ans = max(ans, c)

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 14480
#include <bits/stdc++.h>
using namespace std;
using llong = long long;

void fnInput(llong& rnNumA, double& rnNumB)
{
  cin >> rnNumA >> rnNumB;
}

llong fnMultiple(llong nNumA, double nNumB)
{
  int nNumIB = nNumB * 100 + 0.5;
  return nNumA * nNumIB / 100;
}
  
int main()
{
  llong nNumA;
  double nNumB;

  fnInput(nNumA, nNumB);
  cout << fnMultiple(nNumA, nNumB) << endl;

  return 0;
}

Measured memory_bytes: 3708
import itertools
import bisect

n = int(input())

L = list(map(int,input().split()))

A = sorted(L)

ans = 0

for i in range(n):
    for j in range(i+1,n):
        total = L[i] + L[j]
        ans += bisect.bisect_left(A,total) - (j+1)

print(ans)  

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

int main() {
int a,b;
cin >> a >> b;
int ans = 0;
rep(i,2){
  int x = max(a,b);
  ans += x;
  if(max(a,b) == a) a--;
  else b--;
}
cout << ans << endl;
}
  


Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 1000

int A[NUM],B[NUM];

int main(){

	int N;
	scanf("%d",&N);

	for(int i = 0; i < N; i++){
		scanf("%d",&A[i]);
	}

	int M;
	scanf("%d",&M);

	for(int i = 0; i < M; i++){
		scanf("%d",&B[i]);
	}

	int A_index = 0,B_index = 0;

	while(A_index < N && B_index < M && A[A_index] == B[B_index]){
		A_index++;
		B_index++;
	}

	if(A_index < N && B_index < M){

		if(A[A_index] < B[B_index]){
			printf("1\n");
		}else{
			printf("0\n");
		}

	}else if(A_index == N && B_index < M){

		printf("1\n");

	}else if(A_index < N && B_index == M){

		printf("0\n");

	}else{ // A_index == N && B_index == M

		printf("0\n");
	}

	return 0;
}



Measured memory_bytes: 3176
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
#define mat vector<vector<int>>
const int inf = 1 << 30;
const ll linf = 1e18;
const db EPS = 1e-7;
template<class T> void chmin(T& x, T y){if(x > y) x = y;}
template<class T> void chmax(T& x, T y){if(x < y) x = y;}

int S, W;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> S >> W;
    cout << (S <= W ? "unsafe" : "safe") << endl;
    return 0;
}

Measured memory_bytes: 3640
H, W = gets.chomp.split(" ").map(&:to_i)
A = []
H.times{
  s = gets.chomp
  A << s if s.include?('#')
}

(W-1).downto(1){|i|
  A.map!{|a| a[0..(i-1)] + a[(i+1)..-1]} if A.all?{|a| a[i] == '.'}
}
A.map!{|a| a[1..-1]} if A.all?{|a| a[0] == '.'}

A.each{|a| puts a}


Measured memory_bytes: 1916
import java.io.*;
import java.util.*;

public class Main {
	
	static int N;
	static int[][] dp;
	static int[] a;
	static int[] b;
	static int[] c;
	static int INF = Integer.MAX_VALUE / 2;
		
	public static void main(String[] args) throws IOException {
		FastScanner sc = new FastScanner(System.in);
		
		N = sc.nextInt();
		a = new int[N+1];
		b = new int[N+1];
		c = new int[N+1];
		for(int i = 1; i <= N; i++){
			a[i] = sc.nextInt();
			b[i] = sc.nextInt();
			c[i] = sc.nextInt();
		}
		
		dp = new int[N+1][3];
		
		for(int i = 1; i <= N; i++){
			dp[i][0] = Math.max(dp[i-1][1] , dp[i-1][2]) + a[i];
			dp[i][1] = Math.max(dp[i-1][0] , dp[i-1][2]) + b[i];
			dp[i][2] = Math.max(dp[i-1][0] , dp[i-1][1]) + c[i];
		}
		
		System.out.println(Math.max(dp[N][0], Math.max(dp[N][1], dp[N][2])));
		
	}//end main
	
	/*
	public static int solve(int i){
		
	}
	*/
	
}//end Main

class FastScanner {
    private InputStream in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    public FastScanner(InputStream in) {
		this.in = in;
	}
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() {
    	if (hasNextByte()) return buffer[ptr++];
    	else return -1;
    }
    private static boolean isPrintableChar(int c){
    	return 33 <= c && c <= 126;
    }
    public boolean hasNext() {
    	while(hasNextByte() && !isPrintableChar(buffer[ptr]))
    		ptr++; return hasNextByte();
    }
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }
    public double nextDouble() {
    	return Double.parseDouble(next());
    }
}


Measured memory_bytes: 26892
//#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<utility>
#include<algorithm>
#include<cstring>
#include<sstream>
#include <iomanip>

typedef long long ll ;
typedef double db;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;

#define pf		  	printf
#define sf			  scanf
#define pb(a)         push_back(a)
#define for0(i,n)          for(int i=0;i<n;i++)
#define for1(i,n)          for(int i=1;i<=n;i++)
#define forab(a,b)       for(int i=a;i<=b;i++)
//#define gcd(a, b)     __gcd(a, b)
#define lcm(a, b)     ((a)*((b)/gcd(a,b)))
#define sq(a)		   (a)*(a)
#define nw				"\n"
#define abs(x)		fabs(x)
#define pcase(z,x)     cout<<"Case "<<z<<": "<<x<<"\n"
#define CIN	ios_base::sync_with_stdio(0); cin.tie(0)

using namespace std;

int main()
{
	int i,n;
	cin>>n;
	set<string>s;
	string x;
	for0(i,n){
		cin>>x;
		s.insert(x);
		}
	cout<<s.size()<<nw;
	return 0;
}

Measured memory_bytes: 19088
N = int(input())
S = list(input())
alphabet = ['A', 'B', 'C','D','E','F','G','H','I','J','K','L','M','N','O','P',\
                'Q','R','S','T','U','V','W','X','Y','Z']
idx = []
for s in S:
    idx.append(alphabet.index(s) + N)

for i in range(len(idx)):
    tmp = idx[i]
    while tmp >= 26:
        tmp -= 26
    idx[i] = tmp

for i in idx:
    print(alphabet[i], end='')


Measured memory_bytes: 4596
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
using namespace std;

int main() {
	int n;
	cin>>n;
	vector<long long> a(n);
	for(int i = 0; i < n; ++i) cin>>a[i];
	int c0 = 0, c1 = 0, c2 = 0;
	for(int i = 0; i < n; ++i) {
		if(a[i] % 4 == 0) ++c2;
		else if(a[i] % 2 == 0) ++c1;
		else ++c0;
	}

	if(c0 == 0) {
		cout<<"Yes"<<endl;
	} else if(c0 == 1) {
		if(c2 > 0) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	} else {
		if(c1 == 0) {
			if(c2 + 1 >= c0) cout<<"Yes"<<endl;
			else cout<<"No"<<endl;
		} else {
			if(c2 >= c0) cout<<"Yes"<<endl;
			else cout<<"No"<<endl;
		}
	}
}


Measured memory_bytes: 1024
#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.at(i);
  
  int place = 0;
  string answer = "out";
  int counter = 0;
  for (int i = 0; i < N; i++) {
    counter++;
    place = a.at(place) - 1;
    if (place == 1) {
      answer = "ok";
      break;
    }
  }

  if (answer == "ok") cout << counter << endl;
  else cout << -1 << endl;
}

Measured memory_bytes: 640
#include"bits/stdc++.h"
using namespace std;



int main(void) {

	int N, X, l, count = 1;
	cin >> N >> X;
	vector<int> L(N, 0);

	for (int i = 1; i <= N; i++) {
		cin >> l;
		L[i] = L[i - 1] + l;
		if (L[i] > X) break;
		count++;
	}

	cout << count << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> l_l;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
const int INF=1001001000;
const int mINF=-1001001000;
const ll LINF=1010010010010010000;
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;
}
//グリッド：（典型）dp,dfs,bfs,最短経路,その他
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod){}
mint operator-() const { return mint(-x);}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
mint res(*this);
return res+=a;
}
mint operator-(const mint a) const {
mint res(*this);
return res-=a;
}
mint operator*(const mint a) const {
mint res(*this);
return res*=a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return (*this) *= a.inv();
}
mint operator/(const mint a) const {
mint res(*this);
return res/=a;
}
};
int main(){
    string s;cin>>s;
    ll n=(ll)s.size();
    mint dp[100010][4]={};
    for(int i=n;i>=0;i--){
        for(int j=3;j>=0;j--){
            if(i==n){
                dp[i][j]=(j==3?1:0);
            }
            else{
                dp[i][j]=dp[i+1][j]*(s[i]=='?'?3ll:1ll);
                if(j<3&&(s[i]=='?'||s[i]=="ABC"[j])){
                    dp[i][j]+=dp[i+1][j+1];
                }
            }
        }
    }
    cout<<dp[0][0].x<<endl;
    return 0;
}

Measured memory_bytes: 3584
#define _USE_MATH_DEFINES
#include<cmath>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<iostream>
#include<algorithm>
#include<string>
#include<utility>
#include<tuple>
#include<vector>
#include<list>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<numeric>
#include<functional>
#include<iomanip>
#include<random>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define REP(i,n) for(int i = 0;i < n;i++)
#define FOR(i,a,b) for(int i = a;i < b;i++)
#define ALL(x) (x).begin(),(x).end()
#define dump(x) cout << (x) << endl
#define LMAX 9223372036854775807LL
#define LMIN -9223372036854775807LL
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T &val) {
	fill((T*)array, (T*)(array + N), val);
}

const ll INF = 1e18;

int main() {
	IOS;
	string s;
	cin >> s;
	if (s.size() < 4) {
		dump("No"); return 0;
	}

	dump(s.substr(0,4) == "YAKI" ? "Yes" : "No");
	return 0;
}

Measured memory_bytes: 256
package main

import "fmt"

func main() {
	var S, T, U string
	var A, B int
	fmt.Scan(&S)
	fmt.Scan(&T)
	fmt.Scan(&A)
	fmt.Scan(&B)
	fmt.Scan(&U)
	if U == S{
		A = A - 1
	}else{
		B = B - 1
	}
	fmt.Println(A,B)
}


Measured memory_bytes: 512
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<math.h>
#include<limits>
#include<list>
#include <stdio.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i = 0;i < (n); ++i)
#pragma GCC optimize("Ofast")



int main() {
	int x;
	cin >> x;
	if (x == 1) {
		cout << 0 << endl;
	}
	else {
		cout << 1 << endl;
	}
	return 0;
}


Measured memory_bytes: 3620
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    long n = sc.nextLong();
    long m = sc.nextLong();
    if(Math.abs(m-n)>1){
      System.out.println(0);
      return;
    }
    long nn = 1;
    for(int i = 1;i<=n;i++){
      nn *= i;
      nn %= 1000000007;
    }
    long mm = 1;
    for(int i = 1;i<=m;i++){
      mm *= i;
      mm %= 1000000007;
    }
    nn *= mm;
    if(m == n)nn*=2;
    nn %= 1000000007;
    System.out.println(nn);
  }
}


Measured memory_bytes: 35680
def solve():
    S = input()
    N = len(S)
    for i in range(N - 1):
        if S[i] == S[i + 1]:
            return (i + 1, i + 2)
        if i < N - 2 and S[i] == S[i + 2]:
            return (i + 1, i + 3)
    return (-1, -1)

print(*solve())

Measured memory_bytes: 3188
#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
  int n,k;
  cin >> n >> k;
  int t = 0;
  for (int i=0; i<n; i++){
    int j;
    cin >> j;
    if (j > k/2) {
      t += (k-j)*2;
    } else {
      t += j*2;
    }
  }
 cout << t << endl;  
}

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

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

    int N, M, Q; cin >> N >> M >> Q;
    vector<vector<int>> cs(N, vector<int>(N+1));
    for (int i = 0; i < M; i++) {
        int L, R; cin >> L >> R; L; R;
        cs[L-1][R]++;
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cs[i][j+1] += cs[i][j];
        }
    }
    for (int i = 0; i < Q; i++) {
        int p, q; cin >> p >> q;
        int ans = 0;
        for (int j = p-1; j <= q-1; j++) {
            ans += cs[j][q] - cs[j][p-1];
        }
        cout << ans << "\n";
    }
}

Measured memory_bytes: 1920
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############
S = input()
if (S[0] != S[-1]) ^ (len(S) % 2):
    print('Second')
else:
    print('First')

Measured memory_bytes: 82684
n = int(input())
def decomp(a):
    sqrt = round(n ** 0.5 + 0.5)
    factors = []
    for i in range(2, sqrt + 1):
        if not a % i:
            factors.append(i)
            while a % i == 0:
                a //= i
    if a != 1:
        factors.append(a)
    return factors
phi = n
for i in decomp(n):
    phi *= ((i - 1) / i)
print(int(phi))


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

int main() {
  int N;
  cin >> N;
  
  if (N == 100000)
    cout << 90909 << endl;
  
  else if (N > 9999)
    cout << N - 9090 << endl;
  
  else if (N > 999)
    cout << 909 << endl;
  
  else if (N > 99)
    cout << N - 90 << endl;
  
  else if (N > 9)
    cout << 9 << endl;
  
  else
    cout << N << endl;
}

Measured memory_bytes: 256
N, L = map(int, input().split())
tmp = 1000
ans = 0
if L > 0:
    for i in range(L+1, L+N):
       ans += i

elif L + N - 1 >= 0:
    for i in range(L, L+N):
        ans += i

else:
    for i in range(L, L+N-1):
        ans += i

print(ans)



Measured memory_bytes: 2940
import math

x = input('').split()
x = [int(i) for i in x]
a = x[0]
b = x[1]
h = x[2]
m = x[3]

def root(value):
    return(value ** 0.5)


a_x = a * math.cos(2 * math.pi * ((h + m / 60) / 12))
a_y = a * math.sin(2 * math.pi * ((h + m / 60) / 12))
b_x = b * math.cos(2 * math.pi * (m / 60))
b_y = b * math.sin(2 * math.pi * (m / 60))  

x_x = ((b_x - a_x) ** 2)
y_y = ((b_y - a_y) ** 2)
print(root(x_x + y_y))

Measured memory_bytes: 9604
#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
#define ll long long
#define ull unsigned long long
#define M 1000000007
#define P pair<int,int>
#define PLL pair<ll,ll>
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define RFOR(i,m,n) for(int i=m;i>=n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define PI 3.14159265


int n,m;
int a[1000000];

int main(){
  cin>>n>>m;
  rep(i,n){
    cin>>a[i];
  }

  int ans=1;
  ans +=(n-m)/(m-1);
  ans += ((n-m)%(m-1)!=0);

  cout<<ans<<endl;

  return 0;
}

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

#define int long long int

signed main()
{
    string s,t;
    cin>>s>>t;
    int i,j,n=s.size(),m=t.size();

    int mx=INT_MAX;
    for(i=0;i<=n-m;i++)
    {
        int a=0;
        for(j=0;j<m;j++)
        {
            a+=(s[i+j]!=t[j]);
        }
        mx=min(mx,a);
    }
    cout<<mx<<endl;
}


Measured memory_bytes: 3644
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<iomanip>
#include<set>
#include<numeric>
#include<sstream>
#include<random>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rrep(i, st, n) for (int i = st; i < n; ++i)
using pii = pair<int, int>;
const int inf = 1e9 + 7;
int dy[] = {0, 0, -1, 1};
int dx[] = {1, -1, 0, 0};

int n;
int table[101][101];
int reached[101];
int back[101];
int bn = 1;
int cost = 1;
void dfs(int now) {
    //cout << bn << " " << now << " " << cost << endl;
    rrep(i, 1, n + 1) {
        if (table[now][i] == 1 && reached[i] == 0) {
            cost++;
            reached[i] = cost;
            bn = now;
            dfs(i);
        }
    }
    
    cost++;
    //cout << now << " " << cost << endl;
    back[now] = cost;
    return;
}
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    rep(i, n + 1) rep(j, n + 1) table[i][j] = 0;
    rep(j, n) {
        int u, k; cin >> u >> k;
        int v;
        rep(l, k) {
            cin >> v;
            table[u][v] = 1;
        }
    }
    reached[1] = 1;
    dfs(1);
    rrep(i, 2, n + 1) {
        if (reached[i] == 0) {
            reached[i] = ++cost;
            dfs(i);
        }
    }
    rrep(i, 1, n + 1) cout << i << " " << reached[i] << " " << back[i] << endl;
    
}



Measured memory_bytes: 3244
#include<iostream>
#include<algorithm>
#include<stdio.h>

using namespace std;

int main() {
    int H, W;

    while (cin >> H >> W) {
        if (H == 0) return 0;

        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                if ((i+j)%2 == 0) cout << "#";
                else cout << ".";
            }
            cout << endl;
        }
        cout << endl;
    }


}


Measured memory_bytes: 3104
#include <stdio.h>
#include <ctype.h>

int main(){
    char ch;
    while(1){
        scanf("%c", &ch);
        if(ch=='\n'){
            printf("\n");
            break;
        }else if(islower(ch)){
            printf("%c", toupper(ch));
        }else if(isupper(ch)){
            printf("%c", tolower(ch));
        }else{
            printf("%c", ch);
        }
    }

    return 0;
}


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

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vint;
#define FOR(i,a,b) for(int i=(a);i<(int)(b);i++)
#define rep(i,n) FOR(i,0,n)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define SZ(x) (int)(x).size()
#define ZERO(a) memset(a,0,sizeof(a))
#define dbg(x) cout<<#x<<": "<<(x)<<"\n"
#define pb push_back
#define eb emplace_back
#define mp make_pair

void solve(string s) {
    int n = s.size();
    bool u=0, d=0, l=0, r=0;
    rep(i,n) {
        if(s[i]=='N') u=1;
        if(s[i]=='S') d=1;
        if(s[i]=='E') r=1;
        if(s[i]=='W') l=1;
    }

    if(u and d and r and l) {
        puts("Yes");
    } else if(u and d) {
        if(r or l) puts("No");
        else puts("Yes");
    } else if(r and l) {
        if(u or d) puts("No");
        else puts("Yes");
    } else {
        puts("No");
    }

    return ;
}

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

    return 0;
}


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

using namespace std;

#define LOG(...) fprintf(stderr,__VA_ARGS__)
//#define LOG(...)
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))

typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

int main() {
    int n;
    while(cin >> n, n){
        string preinput;
        string input;

        bool no = 0;
        bool sm_bg = true;

        int min_n = -2000000000;
        int max_n = +2000000000;

        cin >> preinput;
        for(int i = 1;i < n; i++){
            cin >> input;
            if(no) continue;
            if(preinput == input){
                no = true;
                continue;
            }
            if(input == "x"){
                int comp = atoi(preinput.c_str());
                if(sm_bg){
                    min_n = max(comp + 1, min_n);
                }else {
                    max_n = min(comp - 1, max_n);
                }
            }else if(preinput == "x"){
                int comp = atoi(input.c_str());
                if(!sm_bg){
                    min_n = max(comp + 1, min_n);
                }else {
                    max_n = min(comp - 1, max_n);
                }
            }else{
                int a = atoi(preinput.c_str());
                int b = atoi(input.c_str());
                if(sm_bg){
                    if(a > b){
                        no = true;
                        continue;
                    }
                }else{
                    if(a < b){
                        no = true;
                        continue;
                    }
                }
            }

            if(max_n < min_n){
                no = true;
                continue;
            }


            preinput = input;
            sm_bg = !sm_bg;
        }

        // printf("%d %d \n", min_n, max_n);
        if(no){
            cout << "none" << endl;
        }else if (min_n == max_n){
            cout << min_n << endl;
        }else{
            cout << "ambiguous" << endl;
        }
    }
}

Measured memory_bytes: 1228
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<cmath>
#include<climits>
#include<ctime>
#include<cstring>
#include<stack>
#include<queue>
#include<sstream>
#include<string>
#include<set>
#include<array>
#include<cassert>

#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i);

using namespace std;

int main(){
	
	int n;
	cin >> n;
	vector<vector<int>> ans(n,vector<int>(n,0));

	rep(i,n){
		int u,k;
		cin >> u >> k;	
		u--;
		rep(j,k){
			int v;
			cin >> v;
			v--;
			ans[u][v]=1;
		}
	}

	rep(i,n){
		rep(j,n-1){
			cout << ans[i][j] << " ";	
		}
		cout << ans[i][n-1] << endl;
	}

	return 0;
}

Measured memory_bytes: 1256
/* ex5_3
   UMAboogie */
#include<stdio.h>

int main(void){
  int height,width;
  scanf("%d %d",&height,&width); //マスのたての数、横の数を入力
  char grid[height][width]; //マス目の配色を入れる配列
  int row_exist[height]; //その行のマスに黒があるかの真偽値を入れる配列
  int col_exist[width]; //その列のマスに黒があるかの真偽値を入れる配列
  for(int i = 0;i < height;i++){
    for(int j = 0;j < width;j++){
      scanf(" %c",&grid[i][j]); //(i,j)の配色を入力
      if(grid[i][j] == '#'){ //もし黒であれば、各真偽値を1とする
        row_exist[i]=1;
        col_exist[j]=1;
      }
    }
  }
  for(int i = 0;i < height;i++){
    if(row_exist[i] == 1 ){ //まず黒がある行について
      for(int j = 0;j < width;j++){
        if(col_exist[j] == 1){ //黒がある列であれば
          printf("%c",grid[i][j]); //配色を出力
        }
      }
      printf("\n"); //行ごとに改行
    }
  }
  return 0;
}


Measured memory_bytes: 128
# ????????????????±???????????????°??????
import sys

def mul_matrix(a, b):
    n = len(a)
    m = len(b)
    l = len(b[0])
    
    ans = []

    for i in range(n):
        new_row = []
        for j in range(l):
            sum = 0
            for k in range(m):
                sum += a[i][k] * b[k][j]

            new_row.append(sum)

        ans.append(new_row)
    
    return ans

def main():
    n, m, l = [int(i) for i in sys.stdin.readline().strip().split(' ')]
    
    a = []
    b = []
    
    for i in range(n):
        data = [int(j) for j in sys.stdin.readline().strip().split(' ')]
        a.append(data)

    for i in range(m):
        data = [int(j) for j in sys.stdin.readline().strip().split(' ')]
        b.append(data)

    ans = mul_matrix(a, b)

    for i in ans:
        print(' '.join([str(j) for j in i]))
        
if __name__ == '__main__':
    main()
    

Measured memory_bytes: 8916
#include<algorithm>
#include<cstdio>
#define s(A) std::sort(A,A+10);
main(){
int W[10],K[10],p;
for(int i=0;i<20;i++)
scanf("%d",&p),(i<10)?W[i]=p:K[i-10]=p;
s(W);
s(K);
printf("%d %d\n",W[7]+W[8]+W[9],K[7]+K[8]+K[9]);
return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
#define INFTY (1<<15)

int main(){
  double d, t, s;
  cin >> d >> t >> s;

  if(d / s > t) cout << "No" << endl;
  else cout << "Yes" << endl;

  return 0;

}

Measured memory_bytes: 3656
S=str(input())
a=0
b=0
c=0
d=0
for i in range(0,len(S),1):
  if i%2==1 and S[i]=="1": #奇数番目が1
    a+=1
  if i%2==0 and S[i]=="1": #偶数番目が1
    b+=1
  if i%2==1 and S[i]=="0": #奇数番目が0
    c+=1
  if i%2==0 and S[i]=="0": #偶数番目が0
    d+=1

A=a+d
C=b+c
if A>=C:
  print(len(S)-A)
elif A<C:
  print(len(S)-C)

Measured memory_bytes: 3188
#include <iostream>
using namespace std;
 
int main() {
  int N = 0;
  int result = 0;
  cin >> N ;
 
  // ここにプログラムを追記

  if (N % 2 == 0) {
    result = N / 2;
} else {
    result = N / 2 + 1;
}
  cout << result  << endl;
}

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

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

using namespace std;
using ll = long long;
int mod = 1000000007;

vector<int> nodes[100001];

void toposort(int s, vector<int> &order, vector<bool> &seen){
    seen[s] = true;
    for(auto to: nodes[s]){
        if(seen[to]) continue; //探索済み -> スキップ
        toposort(to, order, seen);
    }
    //再帰を抜け出すときにorderに追加
    order.push_back(s);
}

int main(void){
    int N, M; cin >> N >> M;
    int loop = N-1+M;
    int cnt[N+1] = {0};
    vector<int> come[N+1];
    cnt[0] = -1;
    rep(i, loop){
        int from, to; cin >> from >> to;
        nodes[from].push_back(to);
        come[to].push_back(from);
        cnt[to]++;
    }
    vector<bool> seen(N+1, 0);
    vector<int> order;
    for(int i = 1; i <= N; i++){
        if(seen[i]) continue;
        toposort(i, order, seen);
    }

    reverse(order.begin(), order.end());
    
    vector<int> pos_in_order(N+1);
    rep(i, order.size()){
        pos_in_order[order[i]] = i;
    }

    for(int i = 1; i <= N; i++){
        if(come[i].size() == 0) cout << 0 << endl;
        else{
            int par_pos = -1;
            rep(j, come[i].size()) par_pos = max(par_pos, pos_in_order[come[i][j]]);
            cout << order[par_pos] << endl;
        }
    }
    
    return 0;
}

Measured memory_bytes: 17276