stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <iostream>

using namespace std;



int main () {

  int N;

  string S;

  cin >> N >> S;

  int w[300010] = {0};

  int e[300010] = {0};

  if(S[0] == 'W'){

    w[0] = 1;

  }

  else {

    e[0] = 1;

  }

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

    if (S[i] == 'W'){

      w[i] = w[i-1] + 1;

      e[i] = e[i-1];

    }

    else {

      w[i] = w[i-1];

      e[i] = e[i-1] + 1;

    }

  }

  int ans = e[N-1] - e[0];

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

    int count = w[i-1] + e[N-1] - e[i];

    if (count < ans) ans = min(ans, count);

  }

  cout << ans << endl;

}


// Optimized solution to the same problem (faster):
#include "bits/stdc++.h"

using namespace std;

using ll = long long;

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

#define repe(i, begin, n) for (int i = begin; i <= n; i++)

#define repr(i, begin, n) for (int i = begin; i > begin - n; i--)

#define repre(i, begin, end) for (int i = begin; i >= end; i--)



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;

}



const int inf = 1000000007;

const int MOD = 1000000007;

const long long INF = 1000000000000000007;



// -------------------------------------------------------

int N;

string S;

int Easts[301010];



int main() {

  cin >> N >> S;

  rep(i, 0, N) {

    if (S[i] == 'E') {

      Easts[i + 1] = Easts[i] + 1;

    } else {

      Easts[i + 1] = Easts[i];

    }

  }



  int ans = inf;

  repe(i, 1, N) {

    int cost = 0;

    cost += (i - 1) - Easts[i - 1];

    cost += Easts[N] - Easts[i];

    chmin(ans, cost);

  }

  cout << ans << endl;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;



const int maxn=1000000;

int main()

{

    int n,w[maxn],ans,m,tmp;

    char rank[maxn];

    while(~scanf("%d",&n))

    {

        scanf("%s",rank+1);

        fill(w+1,w+n,0);

        for(int i=n;i>=1;i--)

        {

            w[i]=w[i+1];

            if(rank[i]=='W') w[i]++;

        }

        m=w[1];

        ans=maxn;

        for(int i=n;i>=1;i--)

        {

            tmp=((n-i)-w[i+1])+(m-w[i]);

            ans=min(ans,tmp);

        }

        printf("%d\n",ans);

    }

    return 0;

}


// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

using namespace std;

int N,ans=2e9,zj,w,e,W[300005],E[300005];

char S[300005];

int main()

{

	scanf("%d %s",&N,S);

	for(int i=0;i<N;i++)

	{

		if(S[i]=='W')

		w++;

		else

		e++;

		W[i+1]=w;

		E[i+1]=e;

	}

	for(int i=1;i<=N;i++)

	ans=min(W[i-1]+E[N]-E[i],ans);

	printf("%d",ans);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):


#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn=300005;



int n,a[maxn],t,ans=0x3fffffff;

char s[maxn];



int main(){

    scanf("%d",&n),scanf("%s",s+1);

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

        a[i]=a[i-1]+(s[i]=='E');

    t=a[n];

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

        ans=min(ans,(i-1-a[i-1])+(t-a[i]));

    cout<<ans<<endl;

    return 0;

}


// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

using namespace std;

int N,ans=2e9,zj,w,e,W[300005],E[300005];

char S[300005];

int main()

{

	scanf("%d %s",&N,S);

	for(int i=0;i<N;i++)

	{

		if(S[i]=='W')

		w++;

		else

		e++;

		W[i+1]=w;

		E[i+1]=e;

	}

	for(int i=1;i<=N;i++)

	ans=min(W[i-1]+E[N]-E[i],ans);

	printf("%d",ans);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cstdlib>

#include <cstdio>

#include <cstring>

#include <math.h>

#include <queue>

#include <deque>

#include <vector>

#define maxc 100010

#define inf 0x3f3f3f3f

#define ll long long

using namespace std;

int main(){

   int n;

   char a[666666];

   cin>>n;

   for(int i=0;i<n;i++)

        cin>>a[i];

    int sum1=0;

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

        if(a[i]=='E')

            sum1++;

    int sum=sum1;

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

        if(a[i]=='E'&&a[i+1]=='E')

            sum1--;

        if(a[i]=='W'&&a[i+1]=='W')

            sum1++;

        if(sum>sum1)

            sum=sum1;

    }

   cout<<sum<<endl;

   return 0;

}


// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

using namespace std;

int N,ans=2e9,zj,w,e,W[300005],E[300005];

char S[300005];

int main()

{

	scanf("%d %s",&N,S);

	for(int i=0;i<N;i++)

	{

		if(S[i]=='W')

		w++;

		else

		e++;

		W[i+1]=w;

		E[i+1]=e;

	}

	for(int i=1;i<=N;i++)

	ans=min(W[i-1]+E[N]-E[i],ans);

	printf("%d",ans);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h> //Ithea Myse Valgulious

namespace chtholly{

typedef long long ll;

#define re0 register int

#define rec register char

#define rel register ll

#define gc getchar

#define pc putchar

#define p32 pc(' ')

#define pl puts("")

/*By Citrus*/

inline int read(){

  int x=0,f=1;char c=gc();

  for (;!isdigit(c);c=gc()) f^=c=='-';

  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');

  return f?x:-x;

  }

template <typename mitsuha>

inline bool read(mitsuha &x){

  x=0;int f=1;char c=gc();

  for (;!isdigit(c)&&~c;c=gc()) f^=c=='-';

  if (!~c) return 0;

  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');

  return x=f?x:-x,1;

  }

template <typename mitsuha>

inline int write(mitsuha x){

  if (!x) return pc(48);

  if (x<0) x=-x,pc('-');

  int bit[20],i,p=0;

  for (;x;x/=10) bit[++p]=x%10;

  for (i=p;i;--i) pc(bit[i]+48);

  return 0;

  }

inline char fuhao(){

  char c=gc();

  for (;isspace(c);c=gc());

  return c;

  }

}using namespace chtholly;

using namespace std;

const int yuzu=3e5;

typedef int fuko[yuzu|10];

char c[yuzu|10];

fuko sum1,sum2;

int main(){

int n=read(),ans=0x3f3f3f3f;

scanf("%s",c+1);

for (int i=1;i<=n;++i) sum1[i]=sum1[i-1]+(c[i]=='W');

for (int i=n;i;--i) sum2[i]=sum2[i+1]+(c[i]=='E');

for (int i=1;i<=n;++i) ans=min(sum1[i-1]+sum2[i+1],ans);

write(ans);

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

using namespace std;

int N,ans=2e9,zj,w,e,W[300005],E[300005];

char S[300005];

int main()

{

	scanf("%d %s",&N,S);

	for(int i=0;i<N;i++)

	{

		if(S[i]=='W')

		w++;

		else

		e++;

		W[i+1]=w;

		E[i+1]=e;

	}

	for(int i=1;i<=N;i++)

	ans=min(W[i-1]+E[N]-E[i],ans);

	printf("%d",ans);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;



char s[300005];

int cnt1[300005];

int cnt2[300005];

int main()

{

	int n;

	cin>>n>>s;

	int tem1=0,tem2=0;

	memset(cnt1,0,sizeof(cnt1));

	memset(cnt2,0,sizeof(cnt2));

	for(int i=0,j=n-1;i<n;i++,j--)

	{

		cnt1[i]=tem1;

		cnt2[j]=tem2;

		if(s[i]=='W')	tem1++;

		if(s[j]=='E')	tem2++;

	}

	

	int ans=1e8;

	for(int i=0;i<n;i++)

	{

		if(ans>cnt1[i]+cnt2[i])	ans=cnt1[i]+cnt2[i];

	}

	

	cout<<ans<<endl;

	

	

	return 0;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std ;

#define ll long long

void FastInputOutput(){

    ios_base :: sync_with_stdio( 0 ) ;

    cin.tie( 0 ) ;

    cout.tie( 0 ) ;

}



inline int D(){

    int t ;

    scanf( "%d" , &t ) ;

    return t ;

}

inline ll LLD(){

    ll t ;

    scanf( "%lld" , &t ) ;

    return t ;

}

inline ll power(ll x, ll p, ll m){

    ll res = 1;

    while(p){

        if(p & 1)

            res = ((res % m) * (x % m)) % m;

        x = ((x % m) * (x % m)) % m;

        p >>= 1;

    }

    return res % m;

}

long double ModLog(long double base, long double x) {

    return (logl(x) / logl(base));

}

int gcd (int a, int b) {

    while (b) {

        a %= b;

        swap(a, b);

    }

    return a;

}

int lcm(int a, int b){

    return a / gcd(a, b) * b;

}

const ll P = 1e9 + 9;

const int N = 1e6 + 1;



char a[N];

int cml[N], cmr[N];

int main(){

    int n = D();

    scanf("%s", a);

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

        cml[i] = cml[i - 1] + (a[i - 1] == 'W');

    }

    for(int i = n; i > 0; --i){

        cmr[i] = cmr[i + 1] + (a[i - 1] == 'W');

    }

    int ans = INT_MAX;

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

        int el = (i - 1) - cml[i - 1];

        int er = (n - i) - cmr[i + 1];

        ans = min(ans, (cml[i - 1]) + er);

        //printf("pos : %d wl = %d  el = %d wr = %d er = %d\n", i, cml[i - 1], el, cmr[i + 1], er);

    }

    printf("%d", ans);

    

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
//先从左边先行扫描一遍，再从右边扫描一遍，两边加起来直接用总人数相减

    #include <iostream>

    #include <cstring>

    #include <cstdio>

    #include <string>



    using namespace std;



    const int maxn=1e6+10;



    int n;

    int l[maxn],r[maxn];

    char str[maxn];

    int maxx=0;



    int main()

    {

        scanf("%d",&n);

        scanf("%s",str);



        memset(l,0,sizeof(l));

        memset(r,0,sizeof(r));



        for(int i=0;i<n;i++)

        {

            l[i]=l[i-1];

            if(str[i]=='E') {

                    l[i]++;

            }

        }



        for(int i=n-1;i>=0;i--)

        {

            r[i]=r[i+1];

            if(str[i]=='W') {

                    r[i]++;

            }

        }





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

            r[i]=r[i]+l[i];

            maxx=max(r[i],maxx);

         }



         cout<<n-maxx<<endl;









        return 0;

    }


// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

int n,ans=400000;

char a[300010];

int cnt[300010];

int main()

{

	scanf("%d%s",&n,a);

	if (a[0]=='E') cnt[0]=1;

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

	{

		if (a[i]=='E') cnt[i]=cnt[i-1]+1;

		else cnt[i]=cnt[i-1];

	}

	for (int i=0;i<n;i++)

	{

		int t;

		if (i!=0) t=cnt[n-1]-cnt[i]+i-cnt[i-1];

		else t=cnt[n-1]-cnt[i];

		if (ans>t) ans=t;

	}

	printf("%d",ans);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cstring>

#include <cstdio>

#include <cstdlib>

#include <algorithm>



using namespace std;

char s[300010];

int ans1[300010],ans2[300010];

int main()

{

    int N;

    scanf("%d",&N);

    scanf("%s",s);

    memset(ans1,0,sizeof(ans1));

    memset(ans2,0,sizeof(ans2));

    //ans1[0]=1;

    for(int i=0;i<N;i++){

        if(s[i]=='E'){

            ans1[i]++;

        }

        ans1[i+1]=ans1[i];

    }

    //ans2[N-1]=1;

    for(int i=N-1;i>=0;i--){

        if(s[i]=='W'){

            ans2[i]++;

        }

        ans2[i-1]=ans2[i];

    }

    int maxx=0,t;

    for(int j=0;j<N;j++){

        t=ans1[j]+ans2[j];

        maxx=max(t,maxx);

    }

    printf("%d\n",N-maxx);

    return 0;

}


// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

int n,ans=400000;

char a[300010];

int cnt[300010];

int main()

{

	scanf("%d%s",&n,a);

	if (a[0]=='E') cnt[0]=1;

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

	{

		if (a[i]=='E') cnt[i]=cnt[i-1]+1;

		else cnt[i]=cnt[i-1];

	}

	for (int i=0;i<n;i++)

	{

		int t;

		if (i!=0) t=cnt[n-1]-cnt[i]+i-cnt[i-1];

		else t=cnt[n-1]-cnt[i];

		if (ans>t) ans=t;

	}

	printf("%d",ans);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

char mat[105][105];

int dp[105][105], flag[105][105], x, y;

int f(int n, int m)

{

	if(n==0 && m==0){

		if(mat[0][0] == '.')return 0;

		else return 1;

	}

	if(n < 0 || m < 0)return 1000000;

	if(flag[n][m])return dp[n][m];

	int a = f(n,m-1);

	int b = f(n-1, m);

	if(n > 0){

		if(mat[n-1][m] == '.' && mat[n][m] == '#')b++;

	}

	if(m>0){

		if(mat[n][m-1] == '.' && mat[n][m] == '#')a++;

	}

	dp[n][m]=min(a,b);

	flag[n][m]=1;

	return dp[n][m];

}

int main()

{

	// if(mat[0][0] == '.'){

	// 	dp[0][0]=0;

	// }

	// else dp[0][0]=1;

	// flag[0][0]=1;

	scanf("%d%d",&x,&y);

	char dm;

	scanf("%c",&dm);

	for(int i = 0; i < x; i++){

		for(int j = 0; j < y; j++){

			scanf("%c",&mat[i][j]);

		}

		scanf("%c",&dm);

	}

	printf("%d\n",f(x-1,y-1));

	// for(int i = 0; i < x; i++){

	// 	for(int j = 0; j < y; j++){

	// 		printf("%d ",dp[i][j]);

	// 	}

	// 	cout << endl;

	// }

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

using namespace std;



char c[101][102];

int f[101][102];

int main(){

	int n,m;

	scanf("%d%d",&n,&m);

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

		scanf("%s",c[i]+1);

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

		for(int j=1;j<=m;j++){

			if(i==1&&j==1){

				f[i][j]=(c[i][j]=='#');

				continue;

			}

			f[i][j]=2e9;

			if(i!=1)f[i][j]=min(f[i][j],f[i-1][j]+(c[i-1][j]=='.'&&c[i][j]=='#'));

			if(j!=1)f[i][j]=min(f[i][j],f[i][j-1]+(c[i][j-1]=='.'&&c[i][j]=='#'));

		}

	printf("%d\n",f[n][m]);

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



#define endl '\n'



using ll = long long;

using pii = pair<int, int>;

using vi = vector<int>;

using vl = vector<ll>;



#define ff first

#define ss second



#define x first

#define y second



const int N = 200;



pii dir[2] = {

  {1, 0},

  {0, 1}

};



bool a[N][N];

int dp[N][N];



int dfs(pii u, int n, int m) {

  if (u.x == m-1 and u.y == n-1) return a[u.y][u.x];

  if (~dp[u.y][u.x]) return dp[u.y][u.x];

  dp[u.y][u.x] = INT_MAX;

  for (int i = 0; i < 2; i++) {

    pii v = {u.x + dir[i].x, u.y + dir[i].y};

    if (v.x < m and v.y < n) {

      dp[u.y][u.x] = min(dp[u.y][u.x], dfs(v, n, m) + (a[u.y][u.x] and !a[v.y][v.x]));

    }

  }

  return dp[u.y][u.x];

}



int main() {

  ios_base::sync_with_stdio(false);

  cin.tie(nullptr);

  cout.tie(nullptr);



  string s;



  int h, w;

  cin >> h >> w;

  cin.ignore();



  for (int i = 0; i < h; i++) {

    for (int j = 0; j < w; j++) {

      char c; cin >> c;

      a[i][j] = (c == '#');

    }

    cin.ignore();

  }



  memset(dp, -1, sizeof dp);



  int ans = dfs({0, 0}, h, w);



  cout << ans << endl;



  return 0;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;



#define endl '\n'



using ll = long long;

using pii = pair<int, int>;

using vi = vector<int>;

using vl = vector<ll>;



#define ff first

#define ss second



#define x first

#define y second



const int N = 200;



bool a[N][N];

int dp[N][N];



int main() {

  ios_base::sync_with_stdio(false);

  cin.tie(nullptr);

  cout.tie(nullptr);



  int h, w;

  scanf("%d %d ", &h, &w);



  for (int i = 0; i < h; i++) {

    for (int j = 0; j < w; j++) {

      a[i][j] = (getchar() == '#');

    }

    getchar();

  }



  dp[h-1][w-1] = a[h-1][w-1];

  for (int i = h-1, j = w-2; j >= 0; j--) {

    dp[i][j] = dp[i][j+1] + (a[i][j] and !a[i][j+1]);

  }

  for (int i = h-2, j = w-1; i >= 0; i--) {

    dp[i][j] = dp[i+1][j] + (a[i][j] and !a[i+1][j]);

  }

  for (int i = h-2; i >= 0; i--) {

    for (int j = w-2; j >= 0; j--) {

      dp[i][j] = min(

        dp[i+1][j] + (a[i][j] and !a[i+1][j]),

        dp[i][j+1] + (a[i][j] and !a[i][j+1])

      );

    }

  }



  printf("%d\n", dp[0][0]);



  return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <algorithm>

#include <vector>

#include <string>

#include <queue>

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



using namespace std;



using ll = long long;



template<class T>

struct BIT {

  vector<T> dat;



  BIT(int n) : dat(n) {}



  void add(int k, T v) {

    for (int i = k + 1; i < dat.size(); i += i & -i) {

      dat[i] += v;

    }

  }



  T sum(int k) {

    T res = 0;

    for (int i = k; i > 0; i -= i & -i) {

      res += dat[i];

    }

    return res;

  }



  T rsum(int k) {

    return sum(dat.size()-1) - sum(k);

  }



  // sum[0..k) >= v

  int lower_bound(T v) {

    if (v == 0) return 0;

    int k = 0;

    for (int i = dat.size() >> 1; i >= 1; i >>= 1) {

      if (dat[k + i] < v) {

        v -= dat[k + i];

        k += i;

      }

    }

    return k + 1;

  }

};



int main() {

  cin.tie(nullptr);

  ios::sync_with_stdio(false);

  int Q;

  cin >> Q;

  vector<int> type(Q);

  vector<ll> A(Q), B(Q);

  vector<ll> C;

  for (int i = 0; i < Q; i++) {

    cin >> type[i];

    if (type[i] == 1) {

      cin >> A[i] >> B[i];

      C.push_back(A[i]);

    }

  }

  sort(C.begin(), C.end());

  C.erase(unique(C.begin(), C.end()), C.end());

  BIT<int> bit0(1 << 18);

  BIT<ll> bit1(1 << 18);

  int n = 0;

  ll sumb = 0;

  for (int i = 0; i < Q; i++) {

    if (type[i] == 1) {

      sumb += B[i];

      int k = lower_bound(C.begin(), C.end(), A[i]) - C.begin();

      bit0.add(k, 1);

      bit1.add(k, A[i]);

      n++;

    } else {

      int k = bit0.lower_bound((n + 1) / 2);

      ll x = C[k - 1];

      ll ans = sumb + (x * bit0.sum(k) - bit1.sum(k)) + (bit1.rsum(k) - x * bit0.rsum(k));

      cout << x << ' ' << ans << '\n';

    }

  }

}


// Optimized solution to the same problem (faster):
#include <iostream>

#include <algorithm>

#include <vector>

#include <string>

#include <queue>

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



using namespace std;



using ll = long long;

template<class T> using minheap = priority_queue<T, vector<T>, greater<T>>;

template<class T> using maxheap = priority_queue<T, vector<T>, less<T>>;



int main() {

  cin.tie(nullptr);

  ios::sync_with_stdio(false);

  int Q;

  cin >> Q;

  maxheap<ll> L;

  minheap<ll> R;

  ll ans = 0;

  while (Q--) {

    int type;

    cin >> type;

    if (type == 1) {

      ll a, b;

      cin >> a >> b;

      ans += b;

      L.push(a);

      R.push(a);

      if (L.top() > R.top()) {

        ll l = L.top(); L.pop();

        ll r = R.top(); R.pop();

        ans += l - r;

        L.push(r);

        R.push(l);

      }

    } else {

      cout << L.top() << ' ' << ans << '\n';

    }

  }

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

using namespace std;

long long n, m, a, b, c, d[1005][1005];

int main() {

	int i, j, k;

	cin>>n>>m;

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

		for(j=1; j<=n; j++) d[i][j] = -1e18;

		d[i][i] = 0;

	}

	while(m--) {

		cin>>a>>b>>c;

		d[a][b] = c;

	}

	for(k=1; k<=n; k++) for(i=1; i<=n; i++) for(j=1; j<=n; j++)

		if(d[i][k] + d[k][j] > d[i][j]) d[i][j] = d[i][k] + d[k][j];

	d[1][1]>0 ? cout<<"inf" : cout<<d[1][n];

	return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#define N 2010

#define INF 1e18

long long n, m, a[N], b[N], c[N], d[N/2];

int main() {

	int i, j;

	scanf("%lld%lld", &n, &m);

	for(i=0; i<m; i++) scanf("%lld%lld%lld", &a[i], &b[i], &c[i]);

	for(i=1; i<=n; i++) d[i] = -INF;

	d[1] = 0;

	for(i=0; i<n; i++) for(j=0; j<m; j++) {

		if(d[a[j]] != -INF && d[b[j]] < d[a[j]] + c[j]) {

			d[b[j]] = d[a[j]] + c[j];

			if(i==n-1 && b[j]==n) d[0] = 1;

		}

	}

	d[0] ? puts("inf") : printf("%lld", d[n]);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

using namespace std;

long long n, m, a, b, c, d[1005][1005];

int main() {

	int i, j, k;

	cin>>n>>m;

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

		for(j=1; j<=n; j++) d[i][j] = -1e18;

		d[i][i] = 0;

	}

	while(m--) cin>>a>>b>>c, d[a][b] = c;

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

		if(d[i][k] == -1e18) continue;

		for(j=1; j<=n; j++) if(d[i][k] + d[k][j] > d[i][j]) d[i][j] = d[i][k] + d[k][j];

	}

	d[1][1]>0 ? cout<<"inf" : cout<<d[1][n];

	return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#define N 2010

#define INF 1e18

long long n, m, a[N], b[N], c[N], d[N/2];

int main() {

	int i, j;

	scanf("%lld%lld", &n, &m);

	for(i=0; i<m; i++) scanf("%lld%lld%lld", &a[i], &b[i], &c[i]);

	for(i=1; i<=n; i++) d[i] = -INF;

	d[1] = 0;

	for(i=0; i<n; i++) for(j=0; j<m; j++) {

		if(d[a[j]] != -INF && d[b[j]] < d[a[j]] + c[j]) {

			d[b[j]] = d[a[j]] + c[j];

			if(i==n-1 && b[j]==n) d[0] = 1;

		}

	}

	d[0] ? puts("inf") : printf("%lld", d[n]);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#define N 2005

#define INF 1e18

using namespace std;

typedef long long ll;

ll n, m, a[N], b[N], c[N], d[N];

bool f() {

	int i, j;

	for(i=0; i<=n; i++) d[i]=-INF;

	d[1]=0;

	for(i=0; i<=n; i++) for(j=0; j<m; j++) {

		if(d[b[j]] < d[a[j]] + c[j]) {

			d[b[j]] = d[a[j]] + c[j];

			if(i==n && b[j]==n) return 0;

		}

	}

	return 1;

}



int main() {

	cin>>n>>m;

	for(int i=0; i<m; i++) cin>>a[i]>>b[i]>>c[i];

	f() ? cout<<d[n] : cout<<"inf";

	return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#define N 2010

#define INF 1e18

long long n, m, a[N], b[N], c[N], d[N/2];

int main() {

	int i, j;

	scanf("%lld%lld", &n, &m);

	for(i=0; i<m; i++) scanf("%lld%lld%lld", &a[i], &b[i], &c[i]);

	for(i=1; i<=n; i++) d[i] = -INF;

	d[1] = 0;

	for(i=0; i<n; i++) for(j=0; j<m; j++) {

		if(d[a[j]] != -INF && d[b[j]] < d[a[j]] + c[j]) {

			d[b[j]] = d[a[j]] + c[j];

			if(i==n-1 && b[j]==n) d[0] = 1;

		}

	}

	d[0] ? puts("inf") : printf("%lld", d[n]);

	return 0;

}

// Fastest known solution for this problem: