akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef pair<int, int> P;
const int c_INF = 111111111;
const int c_mINF = -111111111;
const int c_YET = -1;
const int c_Dx[4] = { 0,0,1,-1 };
const int c_Dy[4] = { 1,-1,0,0 };
const int c_div = 1000000007; //10^9 + 7


int main() {
	int N, M;
	char S[200][20], T[200][20];
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%s", S[i]);
	}
	scanf("%d", &M);
	for (int i = 0; i < M; i++) {
		scanf("%s", T[i]);
	}

	int ans = 0;
	for (int i = 0; i < N; i++) {
		int now = 1;
		for (int j = i + 1; j < N; j++) {
			if (strcmp(S[i], S[j]) == 0) {
				now++;
			}
		}
		for (int j = 0; j < M; j++) {
			if (strcmp(S[i], T[j])==0) {
				now--;
			}
		}
		ans = max(ans, now);
	}

	if (ans < 0) {
		printf("0");
	}
	else {
		printf("%d", ans);
	}




}

Measured memory_bytes: 128
#include <cmath>
#include <iostream>
#include <map>
#include <string>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

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

  int r_to_w = 0, w_to_r = 0;
  rep(i, n) if (s[i] == 'R') ++r_to_w;
  int ans = max(r_to_w, w_to_r);
  rep(i, n) {
    if (s[i] == 'R') --r_to_w;
    else ++w_to_r;
    ans = min(ans, max(r_to_w, w_to_r));
  }

  cout << ans << endl;

  return 0;
}

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

bool check(vector<int> p, int x){
    rep(i, p.size()){
        if(p[i]==x)return false;
    }
    return true;
}

int main(){
    int x, n;
    cin >> x >> n;
    vector<int> p(n, 0);
    rep(i, n)cin >> p[i];
    
    sort(p.begin(), p.end());
    
    int ans = 10000;
    rep(i, 100){
        if(check(p, x+i)){
            ans = x+i;
        }
        if(check(p, x-i)){
            ans = (x-i<ans)? (x-i) : ans;
        }
        
        if(ans<10000)break;
    }
    
    cout << ans << endl;
    
}

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

#define rep(i, n) for(int i = 0; (int)(i) < n; i++)
 
using namespace std;
 
int main() {
  
  int x, y, z;
  cin >> x >> y >> z;
  cout << z << ' ' << x << ' ' << y << endl;
    
    
}

Measured memory_bytes: 256
#include<stdio.h>

static const int MAX = 500;
static const int INFTY = (1<<21);

main(){
  int n,i,j,u,k,v,c,min;
  int d[MAX],S[MAX],pi[MAX],M[MAX][MAX];

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

  for ( i = 0; i < n; i++ ){
    scanf( "%d %d" , &u, &k);
    for ( j = 0; j < k; j++ ){
      scanf( "%d %d" , &v, &c);
      M[u][v] = c;
    }
  }

  for(i=0;i<n;i++){
    d[i]=INFTY;
    pi[i]=-1;
    S[i]=0;
  }

  d[0]=0;

  while(1){
    min=INFTY;
    u=-1;

    for(i=0;i<n;i++){
      if(!S[i] && d[i]<min){
	u=i;
	min=d[i];
      }
    }

    if(u==-1){
      break;
    }
    S[u]=1;
    
    for(v=0;v<n;v++){
      if(d[v]>d[u]+M[u][v]){
	d[v]=d[u]+M[u][v];
	pi[v]=u;
      }
    }
  }

  for ( i = 0; i < n; i++ ){
    printf("%d %d\n", i, (d[i]==INFTY?-1:d[i]));
  }

  return 0;
}

Measured memory_bytes: 804
#include<bits/stdc++.h>
using namespace std;
 
int main(){
  int n;
  cin >> n;
  int v[n],c[n];
  for(int i = 0; i < n; i++){
      cin >> v[i];
  }
  for(int i = 0; i < n; i++){
      cin >> c[i];
  }
  int ans=0;
  for(int i = 0; i < n; i++){
    if(v[i] - c[i] > 0){
      ans += v[i] - c[i];
    }
  }
  cout << ans;
}

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

using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()

template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a) {
    out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
    out<<'[';
    for(const T &i: a) out<<i<<',';
    out<<']';
    return out;
}
template<class T>
ostream &operator <<(ostream& out, const set<T>& a) {
    out<<'{';
    for(const T &i: a) out<<i<<',';
    out<<'}';
    return out;
}
template<class T, class S>
ostream &operator <<(ostream& out, const map<T,S>& a) {
    out<<'{';
    for(auto &i: a) out<<i<<',';
    out<<'}';
    return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;

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

    ll n, k;
    cin >> n >> k;

    double ret = 0;
    FOR(i, 1, n+1) {
        ll now = i, cnt = 1;
        while(now < k) now *= 2, cnt *= 2;
        ret += 1.0 / (cnt * n);
    }
    cout << fixed << setprecision(15) << ret << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
vector<int> visited;
vector<int> dp;
vector<vector<int> > adj;
vector<int> indegree;
void dfs(int s)
{
    visited[s]=1;
    for(auto it:adj[s])
    {
        indegree[it]--;
        dp[it]=max(dp[it],dp[s]+1);
        if(indegree[it]==0)
        {
            dfs(it);
        }
    }
}
int main()
{
    int n,m;
    cin>>n>>m;
    adj.resize(n+1);
    visited.resize(n+1,0);
    indegree.resize(n+1,0);
    dp.resize(n+1,1);
    for(int i=0;i<m;i++)
    {
        int x,y;
        cin>>x>>y;
        adj[x].push_back(y);
        indegree[y]++;
    }
    for(int i=1;i<=n;i++)
    {
        if(!visited[i]&&indegree[i]==0)
        dfs(i);
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        ans=max(ans,dp[i]);
    }
    cout<<ans-1<<endl;
}

Measured memory_bytes: 14356
/*     ####   ####  #               ####  #        ##   #    # #    # ###### #####
	  #      #    # #              #      #       #  #  ##  ## ##  ## #      #    #
	   ####  #    # #               ####  #      #    # # ## # # ## # #####  #    #
		   # #  # # #                   # #      ###### #    # #    # #      #####
	  #    # #   #  #              #    # #      #    # #    # #    # #      #   #
	   ####   ### # ###### #######  ####  ###### #    # #    # #    # ###### #    #
*/
 
#include<bits/stdc++.h>
using namespace std;
 
typedef long long LL;
typedef vector<LL> VLL;
typedef vector<string> VS;
typedef vector<pair<LL, LL> > VP;
 
 
#define For(in) for (LL i = 0; i < (n); i++)
#define FOR(in) for(LL i=1; i <= (n); i++)
#define pb push_back
#define srt(v) sort(v.begin(), v.end())
#define rev(v) reverse(v.begin(), v.end())
#define uniq(v) v.erase(unique(v.begin(), v.end()), v.end());
#define exit(); return 0;
#define no "NO"
#define yes "YES"
#define con continue;
 
 
LL concate(LL a, LL b)
{
	ostringstream os;
	os <<a <<b;
	istringstream is(os.str());
	LL c;
	is>> c;
	return c;
}
 
LL binpow(LL a, LL b, LL c)
{
	a %= c;
	LL res = 1 ;
	while(b > 0){
		if(b & 1)
		res = res * a % c ;
		a = a * a % c ;
		b >>= 1;
		//cout<<res<<endl;
	}
	return res;
}
 
LL check(char vowel)
{
	return vowel=='a' || vowel=='e' || vowel=='i' || vowel=='o' || vowel=='u';
}
LL mod = 1e9+7;
 
 
int main()
{
	//LL q,t;
	//cin>>t;
	//while(t--)
	//{
	    LL a=0,b=0,c=0,d=0,e=0,f=0,g=0,h=0,i=0,j=0,k=0,l=0,m=0,n=0,o=0,r=0,u=0,w=0,x=0,y=0,z=0;
		LL aa[1000];
		LL flag=0, flag1=0, co=0, co1=0, co2=0, co3=0, x1=0, x2=0, y1=0, y2=0, z1=0, z2=0;
		LL ma=0, mi=100000000;
		LL mid=0, temp=0, stop=0, start=0;
		double pi= 3.141592653589793;
		double d1=0.0, d2, d3, d4;
		VLL v,v1,v2,v3,v4,v5,v6,v7,v8,v9,v10;
		VS vs, vs1, vs2, vs3, vs4;
		VP vp, vp1,vp2;
		char ch, ch1, ch2[1001];
		string str, str1, str2, str3, str4, str5;
		pair<LL, LL> pa;
		list<LL> li, li1;
		map<LL, LL> mp, mp1;
		set<LL> st;
		map<LL ,LL> :: iterator imll;
		VLL :: iterator ivll;
		set<LL> :: iterator isll;
		VP :: iterator ivp;
 

		cin>>n;
		a = n;
		while(a>0)
		{
			x+= a%10;
			a /=10;
		}
		if(n%x==0)cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
		
	//}
	exit()
 
 
}


Measured memory_bytes: 3636
#include<stdio.h>
int main(void){
    int n,m;
    scanf("%d %d",&n,&m);
    int a[m];
    int i;
    for(i=0;i<m;++i){
        scanf("%d",&a[i]);
    }
    int sum;
    sum=0;
    for(i=0;i<m;++i){
        sum+=a[i];
    }
    if(n-sum>=0){
        printf("%d\n",n-sum);
    }else{
        printf("-1\n");
    }
    return 0;
}

Measured memory_bytes: 1704
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		int[] vals = new int[N];
		for (int i = 0; i < N; i++) {
			vals[i] = scan.nextInt();
		}
		Arrays.sort(vals);
		double ans = vals[0];
		for (int i = 1; i < N; i++) {
			ans = (ans + vals[i]) / 2;
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 22868
#include<iostream>
#include<cstdio>
using namespace std;
char s[101];
int main()
{
    cin>>s;
    if(s[0]=='Y'&&s[1]=='A'&&s[2]=='K'&&s[3]=='I') printf("Yes\n");
    else printf("No\n");
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Arrays;
public class Main{
	static ArrayList<Integer>[] map;
	static int[] ch;
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		int m=sc.nextInt();
		map=new ArrayList[n];
		ch=new int[n];
		for(int i=0; i<n; i++){
			map[i]=new ArrayList<>();
		}
		for(int i=0; i<m; i++){
			int a =sc.nextInt()-1;
			int b =sc.nextInt()-1;
			map[a].add(b);
			map[b].add(a);
		}
		Arrays.fill(ch,2);
		if(dfs(0,0)){
			long count=0;
			for(int i=0; i<n; i++){
				if(ch[i]==0){
					count++;
				}
			}
			System.out.println(count*(n-count)-m);
		}else{
			System.out.println((long)n*(n-1)/2-m);
		}
	}
	static boolean dfs(int now,int count){
		if(ch[now]==2){
			ch[now]=count%2;
		}else{
			if(ch[now]!=count%2){
				return false;
			}else{
				return true;
			}
		}
		for(int i:map[now]){
			if(!dfs(i,count+1)){
				return false;
			}
		}
		return true;
	}
}


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

using namespace std;

int main()
{   int n,count=0;
    cin>>n;
 int x=800*n;
    for(int i=1;i<=n;i++)
    {
        if(i%15==0)
        {
            count++;
        }
    }
    int y=count*200;

     cout<<x-y<<"\n";
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <cmath>
#include <ios>
#include <ctype.h>
#include <stack>
#include <istream>
#include <stdio.h>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>
#include <functional>
#include <bitset>
#include <list>
#include <deque>
#include <time.h>
#include <random>
#include <iomanip>
#include <fstream>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define REP(i,a,b) for (int i = a; i < (b); ++i)
#define all(x) (x).begin(),(x).end()
#define pint pair<int,int>
const int INF = 1000000007;
const long double EPS = 1e-15;
const long double PI = acos(-1);
typedef long long ll;
using namespace std;
using Graph = vector<vector<int>>;
using Graph_weighted = vector<vector<pair<int,int>>>;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a,b); }
ll ceil(const ll a, const ll b) { return (a + b - 1) / b; }
int main(){
  int n,m;
  cin >> n >> m;
  Graph G(n);
  vector<ll>h(n);
  rep(i,n)cin >> h[i];
  rep(i,m){
    int a,b;
    cin >> a >> b;
    a--;
    b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  ll ans = 0;
  rep(i,n){
    bool can = true;
    for(auto j : G[i]){
      if(h[i] <= h[j])can = false;
    }
    if(can)ans++;
  }
  cout << ans << endl;
  return 0;
}


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

long x1=0,all=0,x0=0,ans=0;
struct line{
    long be,le,bf;
};
int main(){
    string s;
    cin>>s;
    vector<line> v;
    ref(i,s.size()){
        if(s[i]=='1') x1++;
        if(s[i]=='0'||i==s.size()-1){

        line k;

        all+=x1;
        k.le=x1;
        k.be=all-x1;
        k.bf=x0;

        if(s[i]=='0') x0++;

        if(x1!=0) v.push_back(k);

        x1=0;

        }
    }

    ref(i,all) ans+=(i+2)/2;

    ref(i,v.size()){

        ans+=(x0-v[i].bf)*((v[i].le+1)/2);

        if(v[i].be%2) ans+=((v[i].bf+1)/2)*((v[i].le+1)/2)+(v[i].bf/2)*(v[i].le/2);

        else ans+=(v[i].bf/2)*((v[i].le+1)/2)+((v[i].bf+1)/2)*(v[i].le/2);

    }
    cout<<ans;


}




Measured memory_bytes: 6520
S = input()
Q = int(input())
TFC = [input().split() for _ in range(Q)]
is_reversed = False
head = ''
tail = ''
for tfc in TFC:
    if tfc[0] == '1':
        is_reversed = not is_reversed
    else:
        if tfc[1] == '1':
            if is_reversed:
                tail += tfc[2]
            else:
                head += tfc[2]
        else:
            if is_reversed:
                head += tfc[2]
            else:
                tail += tfc[2]
if is_reversed:
    print(tail[::-1]+S[::-1]+head)
else:
    print(head[::-1]+S+tail)

Measured memory_bytes: 40436
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{
	public static void main(String[] args) throws NumberFormatException, IOException {
		int period = Integer.parseInt(new BufferedReader(new InputStreamReader(System.in), 64).readLine());
		int val = 100;//壱百千円
		for (; 0 < period; period--) {
			val = val * 105 % 100 == 0 ? (int) (val * 1.05) : (int) (val * 1.05) + 1;
		}
		System.out.println(val * 1000);
	}
}

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

void main_()
{
    ll X, Y, A, B, C;
    cin >> X >> Y >> A >> B >> C;
    vector<ll> ps;
    ps.reserve(A);
    copy_n(istream_iterator<ll>(cin), A, back_inserter(ps));
    vector<ll> qs;
    qs.reserve(B);
    copy_n(istream_iterator<ll>(cin), B, back_inserter(qs));
    vector<ll> rs;
    rs.reserve(C);
    copy_n(istream_iterator<ll>(cin), C, back_inserter(rs));

    partial_sort(begin(ps), begin(ps) + X, end(ps), greater<ll>());
    partial_sort(begin(qs), begin(qs) + Y, end(qs), greater<ll>());
    sort(begin(rs), end(rs), greater<ll>());

    vector<ll>::reverse_iterator rit_r(begin(ps) + X);
    vector<ll>::reverse_iterator rit_g(begin(qs) + Y);

    ll ans = accumulate(begin(ps), begin(ps) + X, 0LL)
        + accumulate(begin(qs), begin(qs) + Y, 0LL);
    for (auto r : rs) {
        auto val_r = (rit_r != rend(ps)) ? *rit_r : 1e9 + 7;
        auto val_g = (rit_g != rend(qs)) ? *rit_g : 1e9 + 7;
        if (val_r == 1e9 + 7 && val_g == 1e9 + 7) {
            break;
        }
        auto& rit = (val_r < val_g) ? rit_r : rit_g;
        if (r <= *rit) {
            break;
        }
        ans += r - *rit;
        rit++;
    }

    cout << ans << endl;
}
int main()
{
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);
    main_();
    return 0;
}


Measured memory_bytes: 2560
#include <stdio.h>
int main(){
    int i,j,k;
    int a[100];
    int n;
    int key;
    scanf("%d",&n);
    for(i=0;i<n;i++) scanf("%d",&a[i]);
     
    for(k=0;k<n-1;k++) printf("%d ",a[k]);
     
    printf("%d\n",a[k]);
    for(i=1;i<n;i++){
        key=a[i];
        j=i-1;
        while(j>=0 && a[j]>key){
            a[j+1]=a[j];
            j--;
            }
        a[j+1]=key;
        for(k=0;k<n-1;k++)
          printf("%d ",a[k]);
        printf("%d\n",a[k]);
    }
         
    return 0;
}

Measured memory_bytes: 1760
#include <iostream>

using namespace std;
int main() {
    // std::cout << "Hello, World!" << std::endl;
    long N ,Y;
    cin >> N >> Y;
    for(int yukiti = 0 ; yukiti <= N ; yukiti++){
        for(int itiyo = 0 ; itiyo <= N - yukiti ; itiyo++){
            int souseki = N - itiyo - yukiti;
            long sum = 10000*yukiti + 5000*itiyo + 1000*souseki;
            if(sum == Y){
                cout << yukiti << " " << itiyo << " " << souseki << endl;
                return 0;
            }
        }
    }

    cout << "-1 -1 -1";
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<(b);i++)

int main(){
  int N;cin>>N;
  vector<int> H(N),W(N);
  rep(i,0,N)cin>>H[i]>>W[i];
  int C[4][4];
  int goals[3] = {};
  rep(i,0,4)rep(j,0,4){
    char c;cin>>c;
    if(c=='R')
      C[i][j]=0;
    else if(c=='G')
      C[i][j]=1;
    else 
      C[i][j]=2;
    goals[C[i][j]] |= 1 << (i * 4 + j);
  }
  vector<int> stamps;
  auto inrange = [&](int i,int j) {return 0 <= i && i < 4 && 0 <= j && j < 4; };
  rep(s,0,N){
    rep(i,-3,4)rep(j,-3,4){
      int mask = 0;
      rep(ci,i,i+H[s])rep(cj,j,j+W[s]){
        if(!inrange(ci,cj))continue;
        mask |= (1 << (ci * 4 + cj));
      }
      stamps.push_back(mask);
    }
  }
  queue<int> q;
  q.push(0);
  const int INF = 100;
  vector<int> dp(1 << 16, INF);
  dp[0] = 0;
  while(q.size()) {
    int now = q.front(); q.pop();
    rep(c,0,3){
    for(auto stamp : stamps){
      int next = (~stamp & now) | (goals[c] & stamp);
      if(dp[next] != INF)continue;
      dp[next] = dp[now] + 1;
      q.push(next);
    }
    }
  }
  
  cout << dp[(1 << 16) - 1] << endl;

  return 0;
}



Measured memory_bytes: 3396
import math
from functools import reduce

k = int(input())
total = 0

def gcd(*numbers):
    numbers = numbers
    return reduce(math.gcd, numbers)

for a in range(1, k + 1):
    for b in range(1, k + 1):
        if gcd(a, b) == 1:
            total += 1 * k
            continue
        else:
            for c in range(1, k + 1):
                total += gcd(a, b, c)
print(total)

Measured memory_bytes: 9632
#include<bits/stdc++.h>
using namespace std;
int main ()
{
  int n,k;
  cin>>n>>k;
  int arr[n];
  for(int i = 0;i<n;i++)
  {
    cin>>arr[i];
  }
  for(int i = 0 ; i<n-k;i++)
  {
    if(arr[k+i]>arr[i])
      cout<<"Yes"<<endl;
    else
    cout<<"No"<<endl;
  }
  return 0;
}

      

Measured memory_bytes: 4388
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
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; }

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

  int N; cin >> N;
  string s; cin >> s;
  
  vector<int> W(N, 0), E(N, 0);
  for (int i = 1; i < N; i++) {
    W[i] = W[i-1];
    E[N-1-i] = E[N-i];
    if (s[i-1] == 'W') W[i]++;
    if (s[N-i] == 'E') E[N-1-i]++;
  }
  
  vector<int> ans(N, 0);
  rep(i, N) {
    ans[i] = W[i] + E[i];
  }
  
  cout << *min_element(ans.begin(), ans.end());
}



Measured memory_bytes: 4244
n=input()
p=list(map(int,input().split()))
kazu=0
for i in range(len(p)-2):
    if p[i]<p[i+1] & p[i+1]<p[i+2]:
        kazu+=1
    if p[i]>p[i+1] & p[i+1]>p[i+2]:
        kazu+=1
print(kazu)

Measured memory_bytes: 3060
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define INF 1<<30
#define LINF 1LL<<60

const ll MOD = 1e9+7;
ll powmod(ll a,ll b) {ll res=1;a%=MOD; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%MOD;a=a*a%MOD;}return res;}

int main(void) {
    cin.tie(0); ios::sync_with_stdio(false);
    ll N, M; cin >> N >> M;
    if(abs(N-M) >= 2){
        cout << 0 << endl;
        return 0;
    }
    
    ll max_V = max(N,M);
    vector<ll> fact(max_V+1,0);
    fact[0] = 1;
    for(int i = 1; i <= max_V;i++) (fact[i]= fact[i-1]*i)%=MOD;
    ll min_V = min(N,M);
    
    ll res = fact[max_V] * fact[min_V];
    res %= MOD;
    if(N == M)(res *= 2)%=MOD;
    
    cout << res << endl;
    return 0;
}





Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (int i = j; i < (int)(n); i++)
#define _GLIBCXX_DEBUG
#define MOD 1000000007
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
//name[i][j]-> vvl name(i,vl(j))
//map<int,int>mp
//余りを切り上げる =>  (a + b - 1) / b 

signed main(){
	int n; cin>>n;
	string s; cin>>s;
	ll ans=0;
	rep(i,0,n-1){
		string a,b;
		rep(j,0,n){
			if(j<=i) a.push_back(s[j]);
			else b.push_back(s[j]);
		}
		//cout<<a<<" "<<b<<endl;
		ll cnt=0;
		map<char,int> mp;
		rep(k,0,a.size()) mp[a[k]]++;
		//cout<<mp['a']<<endl;
		set<char> st;
		rep(l,0,b.size()){
			if(mp[b[l]]>0 && !st.count(b[l])){
				cnt++;
				st.insert(b[l]);
			}
		}
		//cout<<cnt<<endl;
		ans=max(ans,cnt);
	}
	cout<<ans;
	
	return 0;
}

Measured memory_bytes: 256
# なぜかうまくいかない
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect, bisect_right, bisect_left

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()    
A = LIST()
# 2 ** 40 > 10 ** 12 ?
tmp = [0] * 40

for a in A:
    for i in range(40):
        if a & (1 << i):
            tmp[i] += 1

# 解説のx
x = 0

for i in range(39, -1, -1):
    # 大きい順にK以下に収めていくのがコツ
    # 2 ** i
    # K以下である かつ tmp[i]の1の数が0の数より小さいなら，
    # 和はより大きくなるので変える
    if x + (1 << i) <= K and tmp[i] < (N + 1) // 2:
        x += (1 << i)
        # x = 11010101...みたいな長さ40のものが出来上がる
# この x が，f(x)を最大とするx
# あとはf(x)をだすだけ
# print(a)
ans = 0
for i in A:
    ans += i ^ x
print(ans)

Measured memory_bytes: 16760
n, k = map(int, input().split())
r, s, p = map(int, input().split())
score_list = list(input())
#rグー、sチョキ、pパー
#for i in range(k):
#    score_list.insert(0, 0)


ans = 0
for i in range(n):
    if score_list[i] == "r":
        if score_list[i] != score_list[i-k] or i < k:
            ans += p
        else:
            score_list[i] = 0
    elif score_list[i] == "s":
        if score_list[i] != score_list[i-k] or i < k:
            ans += r
        else:
            score_list[i] = 0
    elif score_list[i] == "p":
        if score_list[i] != score_list[i-k] or i < k:
            ans += s
        else:
            score_list[i] = 0

print(ans)

Measured memory_bytes: 4084
S = list(input())
n = len(S)+1
a = [0 for _ in range(n)]

for i in range(n-1):
    if S[i] == "<":
        a[i+1] = max(a[i+1], a[i] + 1)

# print(S)
# print(a)
S = S[::-1]
a = a[::-1]
for i in range(n-1):
    if S[i] == "<":
        S[i] = ">"
    else:
        S[i] = "<"

# print("".join(S))
# print(a)
for i in range(n-1):
    if S[i] == "<":
        if a[i] >= a[i+1]:
            a[i+1] = max(a[i+1], a[i] + 1)
# print(a)
print(sum(a))

Measured memory_bytes: 31544
#include <bits/stdc++.h>
using namespace std;
struct Edge {
    int to;     // 辺の行き先
    int weight; // 辺の重み
    Edge(int t, int w) : to(t), weight(w) { }
};
using Graph = vector<vector<int> >;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reprep(i,j,h,w) rep(i,h)rep(j,w)
#define rrep(i,m, n) for(int i = m; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define aall(x,n) (x).begin(),(x).begin()+(n)
#define VEC(type,name,n) std::vector<type> name(n);rep(i,n)std::cin >> name[i];
#define pb push_back
#define pf push_front
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define sum accumulate
#define keta fixed<<setprecision
#define vvector(name,typ,m,n,a)vector<vector<typ> > name(m,vector<typ> (n,a))
#define vvvector(name,t,l,m,n,a) vector<vector<vector<t> > > name(l, vector<vector<t> >(m, vector<int>(n,a)));
typedef long long ll;
const int INF = 2000000000;
const long INF64 = 1000000000000000ll;
const ll MOD = 1000000007LL;
typedef unsigned int uint;

int main(){
  char aa,bb,cc,dd;
  std::cin >> aa>>bb>>cc>>dd;
  int a,b,c,d;
  a=aa-'0';
  b=bb-'0';
  c=cc-'0';
  d=dd-'0';
  char e='+',f='+',g='+';
  //int ee=0,ff=0,gg=0;
  for(int bit=0;bit<(1<<3);bit++){
    int ee=0,ff=0,gg=0;
    int dum=a;
    if(bit&(1<<0))ee=1;
    if(bit&(1<<1))ff=1;
    if(bit&(1<<2))gg=1;
    dum+=pow(-1,ee)*b+pow(-1,ff)*c+pow(-1,gg)*d;
    if(dum==7){
      if(bit&(1<<0))e='-';
      if(bit&(1<<1))f='-';
      if(bit&(1<<2))g='-';
      std::cout << a<<e<<b<<f<<c<<g<<d<<"=7" << std::endl;    
      exit(0);
    }
    
  }
}

Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.stream.IntStream;
import java.io.UncheckedIOException;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author mikit
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        LightScanner in = new LightScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ASortedArrays solver = new ASortedArrays();
        solver.solve(1, in, out);
        out.close();
    }

    static class ASortedArrays {
        public void solve(int testNumber, LightScanner in, PrintWriter out) {
            int n = in.ints();
            int[] a = in.ints(n);
            Boolean inc = null;
            int ans = 1;
            for (int i = 1; i < n; i++) {
                if (a[i - 1] == a[i]) {
                } else if (a[i - 1] < a[i]) {
                    if (inc != null && !inc) {
                        ans++;
                        inc = null;
                    } else {
                        inc = true;
                    }
                } else {
                    if (inc != null && inc) {
                        ans++;
                        inc = null;
                    } else {
                        inc = false;
                    }
                }
            }
            out.println(ans);
        }

    }

    static class LightScanner {
        private BufferedReader reader = null;
        private StringTokenizer tokenizer = null;

        public LightScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
        }

        public String string() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new UncheckedIOException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int ints() {
            return Integer.parseInt(string());
        }

        public int[] ints(int length) {
            return IntStream.range(0, length).map(x -> ints()).toArray();
        }

    }
}



Measured memory_bytes: 40668
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <cstdlib>
#include <utility>
#include <cmath>
#include <queue>
#include <stack>
#include <cstring>

using namespace std;

#define ll long long

#ifndef ONLINE_JUDGE
#define debug(format, ...) fprintf(stderr, \
    "%s:%d: " format "\n", __func__, __LINE__,##__VA_ARGS__)
#else
#define debug(format, ...)
#define NDEBUG
#endif

int h, w, k;
bool grid[10][10];
char s[15];

int main()
{
    scanf("%d%d%d", &h, &w, &k);
    for (int i = 1; i <= h; i++) {
        scanf("%s", s + 1);
        for (int j = 1; j <= w; j++) {
            grid[i][j] = (s[j] == '#');
        }
    }
    int ans = 0;
    for (int rmask = 0; rmask < (1 << h); rmask++) {
        for (int cmask = 0; cmask < (1 << w); cmask++) {
            int cnt = 0;
            for (int i = 1; i <= h; i++) {
                if (rmask & (1 << (i - 1))) continue;
                for (int j = 1; j <= w; j++) {
                    if (cmask & (1 << (j - 1))) continue;
                    if (grid[i][j]) cnt++;
                }
            }
            if (cnt == k) ans++;
        }
    }
    printf("%d", ans);
    return 0;
}


Measured memory_bytes: 1732
let reader = require('readline').createInterface({ input: process.stdin, output: process.stdout, terminal: false});
reader.on('line', line => { main(line) });

function main(line) {
    let [a, b, c] = line.split(" ").map(s => parseInt(s));
    console.log(a + b + c - Math.max(a, b, c));
}

Measured memory_bytes: 7628
n=int(input())
d=list(map(int,input().split()))
m=int(input())
t=list(map(int,input().split()))
d.sort()
t.sort()
di=0
f=0
for ti in range(m):
    if di<n:
        while d[di]!=t[ti]:
            if d[di]>t[ti]:
                f=1
                break
            di+=1
        di+=1
    if f==1:
        break
if f==1:
    print('NO')
else:
    print('YES')

Measured memory_bytes: 127572
def main():
    M_1,D_1 = map(int,input().split())
    M_2,D_2 = map(int,input().split())
    if D_1 == 31:
        print(1)
        return
    
    if D_1 == 30:
        if M_1==4 or M_1==6 or M_1==9 or M_1==11:
            print(1)
            return
        
    if M_1==2 and D_1==28:
        print(1)
        return
    print(0)
    return



if __name__=="__main__":
    main()


Measured memory_bytes: 3060
#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <random>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;

typedef
tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> orderedSet;

#define pb push_back
#define F first
#define S second
#define all(a) (a).begin(), (a).end()

#define for1(i0, l0, r0) for (int i0 = l0; i0 < r0; ++i0)
#define for2(i0, l0, r0) for (int i0 = l0; i0 <= r0; ++i0)
#define forn(i0, n0) for (int i0 = 0; i0 < n0; ++i0)
#define forn1(i0, n0) for (int i0 = 1; i0 < n0; ++i0)
#define forr(i0, n0) for (int i0 = n0; i0 >= 0; --i0)
#define forr1(i0, r0, l0) for (int i0 = r0; i0 > l0; --i0)
#define forr2(i0, r0, l0) for (int i0 = r0; i0 >= l0; --i0)

#define Sort(a) sort(all(a))
#define Reverse(a) reverse(all(a))
#define relaxMax(a, b) a = max(a, b)
#define relaxMin(a, b) a = min(a, b)

typedef long double ld;
#define ui unsigned int
#define ull unsigned long long

typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef pair<string, string> pss;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<ld> vld;
typedef vector<bool> vb;
typedef vector<string> vs;

typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<pdd> vpdd;

typedef vector<vi> vvi;
typedef vector<vd> vvd;
typedef vector<vll> vvll;
typedef vector<vb> vvb;

#define vpss vector<pss>
#define vvs vector<vs>
#define vvpii vector<vpii>
#define vvpll vector<vpll>
#define vpt vector<pt>
#define vvvi vector<vvi>
#define vsi vector<set<int>>
#define ss second
#define ff first

#define printvi(arr) for (int x0 : arr) cout << x0 << ' '; cout << '\n';
#define printvll(arr) for (ll x0 : arr) cout << x0 << ' '; cout << '\n';
#define printpair(pair0) cout << pair0.F << ' ' << pair0.S << '\n';
#define printvp(arr) for (auto pair0 : arr) printpair(pair0);
#define initArray(arr, N0, X0) memset(arr, X0, N0 * sizeof(int))
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void init() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //cout.precision(16);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
}

void solve() {
    string s;
    cin >> s;
    vi cnt(26);
    for (char c : s) cnt[c - 'a']++;
    forn(i, 26){
        if (cnt[i] % 2 == 1){
            cout << "No\n";
            return;
        }
    }
    cout << "Yes\n";
}

bool multitest = false;

int main() {
    init();
    int t = 1;
    if (multitest) cin >> t;
    forn(i, t) solve();
}

Measured memory_bytes: 3656
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define mk make_pair
#define fi first
#define se second
#define vll vector<ll>
#define pii pair<ll,ll>
#define vvll vector< vector<ll> >
#define pb push_back
#define sz(v) (v).size()
#define inf 1e18
#define md 1000000007
#define all(v) (v).begin(),(v).end()
#define rep(i,a,b) for(ll i=a;i<b;++i)
#define tel(a){cout<<a<<"\n";}
#define tell(a,b){cout<<a<<" | "<<b<<"\n";}
#define telll(a,b,c){cout<<a<<" | "<<b<<" | "<<c<<"\n";}
#define teln(v,n){cout<<"v- ";rep(i,0,n)cout<<v[i]<<" ";cout<<"\n";}
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define tihs if(fopen("inp.txt","r"))freopen("inp.txt", "r", stdin),freopen("out.txt", "w", stdout);
using namespace std;
#define TRACE
 
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
 

#define M 200010


int main(){
	IOS;
	tihs;
	
	ll a[3][3];
	rep(i,0,3)rep(j,0,3)cin>>a[i][j];
	ll n;cin>>n;
	set<ll>s;
	ll b[n];
	rep(i,0,n)cin>>b[i],s.insert(b[i]);
	ll c[3][3];
	rep(i,0,3)rep(j,0,3){
		if(s.count(a[i][j]))c[i][j]=1;
		else c[i][j]=0;
	}
	bool ok=0;
	rep(i,0,3){
		ll cnt=0;
		rep(j,0,3)if(c[i][j])cnt++;
		if(cnt==3)ok=1;
	}
	rep(j,0,3){
		ll cnt=0;
		rep(i,0,3)if(c[i][j])cnt++;
		if(cnt==3)ok=1;
	}
	if(c[0][0]+c[1][1]+c[2][2]==3)ok=1;
	if(c[2][0]+c[1][1]+c[0][2]==3)ok=1;
	if(ok)cout<<"Yes";
	else cout<<"No";



	
	return 0;
}

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

#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define eb emplace_back

typedef long long ll;
typedef pair<int,int> ii;
typedef vector< pair<int,int> > vii;
const ll INF = 0x3f3f3f3f3f3fef;

const int V = 1e5+2;
const int N = 102;

ll dp[V];
ll p[N];
ll v[N];
ll n,w;
 
int main() {
    ios_base::sync_with_stdio(false);
    for(int i = 0; i < V; i++) dp[i] = INF;

    cin >> n >> w;
    for(int i = 0; i < n; i++) cin >> p[i] >> v[i];
    
    dp[0] = 0;
    for(int i = 0; i < n; i++) 
        for(ll j = V-1; j-v[i] >= 0; j--)
            if(dp[j-v[i]] != INF) dp[j] = min(dp[j], dp[j-v[i]]+p[i]);

    for(int i = V-1; i >= 0; i--)
        if(dp[i] <= w) { cout << i << endl; return 0; }


    return 0;
}



Measured memory_bytes: 1024
#pragma region header
#include <bits/stdc++.h>
using namespace std;
#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 rev(i, n) for(int i = (int)(n - 1); i >= 0; i--)
#define rev1(i, n) for(int i = (int)(n); i > 0; i--)
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define resort(v) sort((v).rbegin(), (v).rend())
#define vi vector<int>
#define vvi vector<vector<int>>
#define vc vector<char>
#define vvc vector<vector<char>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
using ll = long long;
using P = pair<int, int>;
/* ----------------よく使う数字や配列----------------- */
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
constexpr ll mod = 1e9+7;
constexpr ll inf = INT32_MAX/2;
constexpr ll INF = LLONG_MAX/2;
constexpr long double eps = DBL_EPSILON;
constexpr long double pi = 3.141592653589793238462643383279;
/* ----------------------end----------------------- */

/* --------------------テンプレート------------------ */
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;
}
/* ----------------------end----------------------- */

/* --------------------ライブラリ-------------------- */
ll fact(int i) {       //階乗
    if (i == 0) return 1;
    return (fact(i - 1)) * i;
}
ll gcd(ll a, ll b) {        //最大公約数
    if(b == 0) return a;
    return gcd(b, a % b); 
}
ll lcm(ll a, ll b) {      //最小公倍数
    return a * b / gcd(a, b);
}
int keta(ll n) {        //桁数を求める
    if(n == 0) return 1;
    int count = 0;
    while(n != 0) {
        n /= 10;
        count++;
    }
    return count;
}
ll ketasum(ll n) {    //各桁の和
    ll sum = 0;
    while(n != 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
/* ----------------------end----------------------- */
#pragma endregion
int main() {
    ll a,b;cin >> a >> b;
    if(a==1||b==1) {
        cout << 1 << endl;
        return 0;
    }
    if(a*b%2==0) cout << a*b/2 << endl;
    else cout << a*b/2+1 << endl;
    return 0;
}

Measured memory_bytes: 3556
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cassert>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <limits>
#include <numeric>
#include <utility>
#include <deque>
#include <valarray>
#include <unordered_set>
#include <unordered_map>
#include <regex>
#include <array>
#include <bitset>
#include <complex>
#include <string>
#include <tuple>

using namespace std;
using ll = long long;
const int INF = 1e9;
const int MOD = 1e9 + 7;

int main()
{
  int a, b;
  cin >> a >> b;
  int sum = 0;
  for (int i = 1; i <= b - a; ++i)
    sum += i;
  cout << sum - b << endl;

  return 0;
}


Measured memory_bytes: 256
import heapq


class Dijkstra:

    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        num_of_city = len(self.rote_map)
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
        if self.goal_point is not None:
            return self.get_path(self.goal_point, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))

n,m=map(int, input().split()) 
route_map = [dict() for _ in range(n)]

for i in range(m):
    u, v, a = map(int, input().split())
    u, v = u - 1, v - 1
    if v in route_map[u].keys():
        a = min(a, route_map[u][v])
    route_map[u][v] = a


    
for i in range(n-1):
    u, v = i+1, i
    route_map[u][v] = 0
    

# ゴールまでの最短経路
dijkstra_result = Dijkstra(route_map,0).execute()


if dijkstra_result[-1]!=float('inf'):
    print(dijkstra_result[-1])

else:
    print(-1)


    
    
    
    
        
    

 






        
    
    
    
    
    
        
    

 






        
        


        
    
    
    
    
    
        
    

 






        
    
    
    
    
    
        
    

 






        
        


        
    
    
    
    
    
        
    

 







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

int main() {
    int m;
    while(cin >> m, m) {
        vector<int> a(m), b(m);
        for(int i=0; i<m; ++i) {
            cin >> a[i] >> b[i];
        }
        vector<vector<int>> dp(m+1, vector<int>(1001));
        dp[0][0] = 1;
        for(int i=0; i<m; ++i) {
            for(int j=0; j<1001; ++j) {
                for(int k=0; k*a[i]+j<1001 && k<=b[i]; ++k) {
                    dp[i+1][j+k*a[i]] += dp[i][j];
                }
            }
        }
        int g;
        cin >> g;
        while(g--) {
            int n;
            cin >> n;
            cout << dp[m][n] << endl;
        }
    }
}


Measured memory_bytes: 3148
#include<stdio.h>
int main()
{
    int n,m,c=0,s;
    scanf("%d%d",&n,&m);
    int a[m+1];
    for(int i=0;i<m;i++)
    {
        scanf("%d",&a[i]);
        c=c+a[i];
    }
    s=n-c;
    if(c>n)
        printf("-1\n");
    else
        printf("%d\n",s);
    return 0;
}


Measured memory_bytes: 1732
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
#define inf (int)(1e9+7)
#define INF (ll)(1e18)
#define abs(x) (x >= 0 ? x : -(x))
#define lb(v, x) (int)(lower_bound(all(v), x) - v.begin())
#define ub(v, x) (int)(upper_bound(all(v), x) - v.begin())
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<typename T> T pow(T a, int b) { return b ? pow(a * a, b / 2) * (b % 2 ? a : 1) : 1; }



set<int> calc(int x) {
    set<int> s;
    for (int i = 1; i * i <= x; ++i) {
        if (x % i == 0) {
            s.insert(i);
            s.insert(x / i);
        }
    }
    return s;
}

void solve() {
    int n;
    cin >> n;
    
    int cnt = 0;
    for (int i = 1; i <= n; i += 2) {
        auto s = calc(i);
        if (sz(s) == 8) {
            cnt++;
        }
    }
    cout << cnt << endl;
}

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





Measured memory_bytes: 256
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define pii pair<int, int>
#define endl '\n'
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define vpii vector<pii>
#define vvpii vector<vpii>
typedef long long ll;
typedef long double ld;
using namespace std;
template<class T> using minheap = priority_queue<T, vector<T>, greater<T>>;
template<typename T> void setmax(T& a, T b) { a = max(a, b); };
template<typename T> void setmin(T& a, T b) { a = min(a, b); };
template<typename T> bool in(T v, T lo, T hi) { return lo <= v && v <= hi; };

const int N = 2e5 + 10;
ll inv10[N];

ll power(ll a, ll b, ll mod) {
  if (b == 0) return 1 % mod;
  ll c = power(a, b / 2, mod);
  c = c * c % mod;
  if (b & 1) c = c * a % mod;
  return c;
}

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

  int n, p;
  string s;
  cin >> n >> p >> s;

  if (p == 2 || p == 5) {
    ll ans = 0;
    for (int i = 0; i < n; i++) {
      int d = s[i] - '0';
      if (p == 2) {
        if (d % 2 == 0) {
          ans += i + 1;
        }
      }
      if (p == 5) {
        if (d % 5 == 0) {
          ans += i + 1;
        }
      }
    }
    cout << ans << endl;
    return 0;
  }

  inv10[0] = 1;
  inv10[1] = power(10, p - 2, p);
  for (int i = 2; i < N; i++) {
    inv10[i] = inv10[i - 1] * inv10[1] % p;
  }
  ll ans = 0, pref = 0;
  map<ll, ll> cnt;
  cnt[0] = 1;
  for (int i = 0; i < n; i++) {
    int d = s[i] - '0';
    pref = (10 * pref + d) % p;
    ll target = pref * inv10[i] % p;
    ans += cnt[target];
    cnt[target]++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 2580
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define mx INT_MAX
#define mn INT_MIN
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define itr set<int> :: iterator
const int mod = 1e9+7;
const ll inf = 1e18+5;

vector<int> a;
ll dp[401][401];


ll s(int l, int r){
  
  ll sum = 0;
  for(int i=l; i<=r; i++){
    sum += a[i];
  }

  return sum;
}

int main(){
    // ******* START HERE ******
    
    int n;
    cin>>n;

    for(int i=0; i<n; i++){
      int x;
      cin>>x;
      a.pb(x);
    }
    
    memset(dp, 0, sizeof(dp));
    
    for(int l = n-1; l>=0; l--){
       for(int r = l; r<n; r++){
          if(l==r)
            dp[l][r] = 0;
          else{
            dp[l][r] = inf;
            for(int i=l; i<=r-1; i++){
              dp[l][r] = min(dp[l][r], dp[l][i] + dp[i+1][r] + s(l,r) );
            }
          }
       }
    }

    cout<<dp[0][n-1]<<endl;

    // ***** END HERE ***** 
    return 0;
}

Measured memory_bytes: 4840
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    ans = n * (n + 1) // 2
    n_3 = n // 3
    n_5 = n // 5
    n_15 = n // 15
    ans -= n_3 * (n_3 + 1) * 3 // 2
    ans -= n_5 * (n_5 + 1) * 5 // 2
    ans += n_15 * (n_15 + 1) * 15 // 2
    print(ans)

main()

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

typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll, ll> pii;
typedef vector<pii> vii;
typedef map<ll, ll> mii;
const int MOD = 1e9 + 7;

#define fastIO() \
ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define endl "\n"
#define pb push_back
#define ff first
#define ss second
#define mp make_pair 

string K;
int D;

int main() {
    cin >> K >> D;
    int n = K.length();
    vector<vi> dp(D, vi(2));
    // dp[i][j] says how many nums such that sum is i mod D and 
    // j = 0 indicates smaller than K so far, j = 1 indicates moving at full capacity
    for (int i = 0; i < K[0]-'0'; ++i) {
        dp[i % D][0] += 1;
    }
    dp[(K[0] - '0') % D][1] = 1;
    for (int i = 1; i < n; ++i) {
        vector<vi> new_dp(D, vi(2));
        for (int sum = 0; sum < D; ++sum) {
            for (int digit = 0; digit < K[i] - '0'; ++digit) {
                new_dp[(sum + digit) % D][0] += (dp[sum][0] + dp[sum][1]);
                new_dp[(sum + digit) % D][0] %= MOD;
            }
            new_dp[(sum + K[i] - '0') % D][0] += dp[sum][0];
            new_dp[(sum + K[i] - '0') % D][0] %= MOD;
            new_dp[(sum + K[i] - '0') % D][1] += dp[sum][1];
            new_dp[(sum + K[i] - '0') % D][1] %= MOD;
            for (int digit = K[i] - '0' + 1; digit <= 9; ++digit) {
                new_dp[(sum + digit) % D][0] += dp[sum][0];
                new_dp[(sum + digit) % D][0] %= MOD;
            }
        }
        // for (int j = 0; j < D; ++j)
        //     cerr << dp[j][0] << " " << dp[j][1] << endl;
        // cerr << "*" << endl;
        dp = new_dp;
    }
    // for (int j = 0; j < D; ++j) cerr << dp[j][0] << " " << dp[j][1] << endl;
    //     cerr << "*" << endl;
    ll ans = dp[0][0] + dp[0][1];
    ans = (ans + MOD - 1) % MOD;    //subtracting num = 0 case
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256